COMP2521 26T2 Week 7 Lecture 2

[00:00:50]Hello everyone.

[00:01:14]Okay.

[00:01:28]Wow.

[00:01:34]Hello everyone. Can you hear me?

[00:01:41]Any question from last session?

[00:01:50]Okay. Why is not Okay, no question.

[00:02:12]So we have two more topics uh to discuss today about graph and then they will finish.

[00:02:22]We will have two more session.

[00:02:25]one is about trees again and another hash table. So uh if you remember last week we last session we discussed three different topics regarding directed graph finding um traversal finding cycle and also transitive closure and today we talking about dystra algorithm which is about finding the shortest path between vertics and also minimum spanning tree that we will discuss today also.

[00:03:04]So let's see what is this Dextra algorithm.

[00:03:09]Um if you remember in directed graph each edge has a direction. So we have a source and destination.

[00:03:18]But here we want to uh actually discuss weighted directed graph. So we have a um edge between two nodes and also each one has a weight. This weight based on the problem can be distance can be cost or whatever.

[00:03:39]Regardless what is this weight? We want to see how we can find shortest path between two nodes. But here because we have a weight the shortest path here the path has a shortest uh cost or distance between two nodes. We know that in undirected graph when we talking about shortest path it means the minimum number of edges between two nodes. But here is not about the minimum number of edges it's about minimum total cost or distance between between two uh vertics.

[00:04:17]So we are trying finding the path between two vertics with a uh minimum cost.

[00:04:26]So overall when we are talking about finding a shortest path between two vertics we can have three different type of problems. First is source and target.

[00:04:40]So we have one source in a graph, a source vertx, a target vertx, and we want to just find the shortest path between this single source and single target.

[00:04:53]Another category is uh single source. It means we have a single source but we want to find the shortest path between this single source and any other vertex in the graph.

[00:05:09]And the last is all pairs. So we want to find the shortest path between any pair of the vertex dystra algorithm is with for the second one. So we are discussing about how we find the shortest path between a single source. So we choose one vertex and then we want to find what is the shortest distance or shortest path between this vertex versus all other vertics in the graph.

[00:05:40]So in weighted graph this is important that sometimes uh using multiple ages to find the path uh has a total um less cost compared to use a direct edge between two vertics.

[00:05:58]For example here we have a vertex zero and vertex one. If we choose the direct path between zero and one the cost is five. But if we go from 0 to two and then two to one the cost is four. So here actually the number of edges is not matter between source as destination the cost or distance is matter that which one has the shortest cost or distance.

[00:06:27]But as I said in unirected graph the definition is different because there the number of edges between source and destination is important.

[00:06:37]Any question so far?

[00:06:43]So the algorithm that we are discussing the name is Dystra. That's the name of the person a Dutch computer scientist who uh introduced this algorithm.

[00:06:56]uh so as I said in dyra algorithm we're trying to find the shortest path in a weighted graph with non negative weights. So this condition is very important because if you have a graph that has a negative weight then diccastra is not working. We we need to use some other algorithm and dicostra algorithm can work on directed and undirected doesn't matter but it should be weighted and weights should not be negative.

[00:07:33]Uh here a summary of how this algorithm actually works and then we will see the example it will be more clear that what how actually we are finding the shortest path uh between two nodes.

[00:07:52]Uh the first important point is as I mentioned in Dextra algorithm you are finding shortest path between one source uh and all other vertex. So it is a single source problem uh when you're using Dcastra.

[00:08:10]So we start from source and gradually expand uh to find the closest reachable vertex.

[00:08:19]Each time when we start dcastra algorithm we pick one vertx and do all the process on that vertx you will see and then we keep it side and go to the next one. So every stage we actually find the shortest paths uh against one single node and then we proceed to the next vertex. So in each stage we select one of the vertex from the unprocessed one that you will see what does it mean the one that has the shortest known distance so far and then we find u apply the dichestra algorithm on that single vertex and then go for the next one.

[00:09:03]uh and each time when we choose a vertx we will check that if we use this vertx can we find a shorter uh path or not and if we find a shorter path we have few data structure that you will see we have to update that data structure first data structure about saving the distance we need to update this one and also uh we need to update the predecessor data structure Here also overall we have three data structure in Dextra. One is distance array will keep the shortest distance that we already find between our source and other vertx and it can be updated during the algorithm and at the end we find the shortest distance between source and any other vertx. Another data structure that we are using is predecessor is the same thing that we using for BFS DFS. It u actually keep track of the parent or the node that we uh from that node will reach to the current vertex.

[00:10:19]And the third data structure is set of vertx and it shows that which vertx is already processed which one is not processed and every time we select one of them from this set and then apply diccastro algorithm on that. So overall we have a three data structures that we use. You will see how we use this tree.

[00:10:44]So overall uh first we need to create and initialize all these three data structures.

[00:10:54]Uh first we create distance array and initialize it with in infinity all of them.

[00:11:02]And then we create predecessor array and initialize it to minus one. And also we initialize a set of vertx uh to list of the vertics that we have in the graph.

[00:11:14]And every time we choose one and process that particular vertx and also at the start point we set the distance of the source to zero because when I am at source my distance to source is zero. So always the distance to source is zero and as long as still there is a vertx that is not processed yet we have to remove one of them from set of vertics the one that has a smallest distance and then apply edge relaxation on it that this is the main operation of dicestra that we'll discuss what does it mean edge relaxation this is overall how dichestra algorithm work we will see an example So as I mentioned this is the most important operation of dicestra edge relaxation. So let's see what does it mean.

[00:12:14]Uh suppose uh this is a source node and this is one of the nodes that we want to find the shortest path between S and W.

[00:12:30]And suppose the current known distance uh minimum distance between S to W is this W. This is the known shortest path between S and W. And also we have the shortest known path between S and V. In H relaxation we want to know that if we come from S to V and then V to W will give us a shorter distance or not. If it give us a shorter distance then we will update this this W. So this is called short uh uh edge relaxation. So we are trying to see if we use v to reach w will give us a shorter distance or not.

[00:13:26]So if this plus weight give us a smaller number compared to this w then we updated this w with this uh actually number and also we update the predecessor also because now the predecessor should be v because we are reaching w through v. Let's see few examples.

[00:13:53]If you understand this part, the rest is very easy. This is the most important part of uh Dextra algorithm. Suppose uh this is a dist array that showing um u minimum distance between source versus any other nodes in the graph so far.

[00:14:15]And predecessor show that from which node we reach the destination.

[00:14:22]And this is our graph part of the graph.

[00:14:25]Suppose so far the shortest path that we find from S to U is five.

[00:14:33]And here we can see that this is already in the distance array that shortest path so far to U is five and shortest path so far to W is infinity. Now we want to see if we go to W through U can give us a smaller number or smaller distance or not. So if you sum five + 7 it will be 12 which is smaller than infinity. So instead of infinity you will replace it with 12 and also uh you will update the predecessor that you access W through node u. So this called edge relaxation. So the previous shortest distance was infinity. Now we found an uh shorter uh distance compared to previous one. So we replace it 5 + 7 12 is less than infinity. So we replace infinity with 12 and update the predecessor. Any question here?

[00:15:52]Okay. Another example.

[00:15:56]This distance array said that so far the shortest distance to U is five.

[00:16:02]Shortest distance to V is 8 and shortest distance to W is 12. Now we want to see if we come to W through V. It will give us a again shorter distance or not. So far the shortest distance between S and W is 12 that we can see here. Now if we come from S to V the shortest distance so far is 8 + 3 is 11 and 11 is less than 12. So we will replace 12 with 11 and also update U to V because now the shortest path known to V to W is true V.

[00:16:48]So every time we have to update and find the shortest path and at the end we will have shortest path to versus each vertx in distance array and also we can use this predecessor to access and find the shortest path between any two um between source and any vertx. Any question here?

[00:17:19]So this is the sudo code. We create distance array initialize it to infinity. We create predecessor initialize this to minus one. And also we have a v set that contain all vertics initially. And then we set the distance of source to zero. And also as long as we have a node that we are not processed and it is in v set, we select one of them that has a minimum distance so far and then remove it from v set and apply edge relaxation if it is applicable in that particular ed. um edge. So let's see example that it will be more clear that how it's all working.

[00:18:08]Let me show you here.

[00:18:16]So this is a graph and we want to find the shortest path between zero and any other vertex in this graph. So we want to find the shortest path between 0 to 1, 0 to 2, 0 to 3, 0 to 4 and 0 to 5.

[00:18:34]The source is always fixed.

[00:18:40]We initialize the distance array as I said always for the source we keep zero and the rest infinity and predecessor also we initialize with minus one. and we said have the list of the nodes in the graph. The initially we have all of this because we haven't processed it yet.

[00:19:05]So this is a start point.

[00:19:09]Now we want to start from zero. So we remove zero from v set and try uh and start exploring zero.

[00:19:23]First uh we start from zero. We try to uh uh see or apply edge relaxation between 0 to one and then we do from 0 to two and then versus 0 to three. We check all other vertex that directly connected to the zero.

[00:19:44]So we have to calculate uh distance the known shortest distance so far to zero plus the weight of the edge that take us to the one. So the shortest distance to zero is already zero if you check the distance array. So 0 + 14 will be 14. Then we have to check that if this 14 is less than known distance to one already. We see that in the distance array the shortest known path to what is already infinity and we found 14. But because 14 is less than infinity. So we update the distance and print. So now the shortest distance to one from the source is 14. And the node that we actually reach to one is true zero. So we update node one.

[00:20:47]Next we have to check 0 versus two.

[00:20:52]Now we want to check 0 versus two. We have to calculate um distance 0 + 9. So the distance 0 is 0 + 9 will be 9. We compare it with the uh minimum distance to two so far which is infinity. 9 is less than infinity. So we replace infinity with nine and then update predecessor also.

[00:21:23]How about next one which is three distance 0 is 0 + 7 will be 7 and 7 is less than infinity. So we update node three also the shortest node from 0 to three so far is seven through vertex zero. So we processed zero node zero finished and now we should take another vertx and apply edge relaxation again.

[00:21:59]Any questions so far?

[00:22:06]So we process zero. Now we have to pick another vertex and uh repeat whole process. But which one we have to select? This is important. Should I uh next stage go to one, two, three, four or five? We have to look at the distance array and see which one has a minimum distance so far and we take that node.

[00:22:33]So already zero is processed. We so we never check zero anymore. It's finished.

[00:22:39]So the distance to one is 14 to two is 9 to three is 7 4 5 infinity. So between among all these nodes three has the shortest non distance so far. So next node that we have to process is node three. So this is how we select each node in dystra algorithm. So next is three. So we're removing tree from v set and start applying dextra algorithm on the node tree.

[00:23:10]We want to explore node tree.

[00:23:15]Okay. Three has three uh actually uh edges connected to three. Three to zero 3 to two and 3 to 5. We already explode zero. So we ignore this edge. You don't need to calculate this. If there is a edge to a node that already explored, you ignore it. You don't need to do all this calculation again. So we ignore this edge. You don't need to do any update or calculation here.

[00:23:47]Next is sorry next is this edge 3 to two. So what you need to calculate is distance 3 + 10.

[00:24:01]What is the known distance to three yet is seven? 7 + 10 17.

[00:24:10]So then you check if 17 is smaller than or less than the known distance to three. We know that the shortest distance now so far is seven and this one is 17. So you don't need to update it because you didn't find a shortest distance. So no update here.

[00:24:33]Next we have to have a look to this one three and five. So we have to again calculate this three + 15. This three is 7. 7 + 15 is 22 and 22 is larger than 7.

[00:24:50]So no update again.

[00:24:54]Oh sorry that was five. Five was infinity and this is 22. 22 is smaller than 15 infinity. So we update for node five.

[00:25:06]So we explored node three also. So node zero and node three already explored and we do not check these two nodes anymore.

[00:25:17]Now except for zero and three we have to check to find which one has the shortest distance and then we we will pick that note. So 1 is 14, 2 is 9, 4 is infinity and 5 is 22. Among these four, two has a shortest distance so far. So next node that we need to explore is node two.

[00:25:43]Node two has four connection, four edges 2 to 0, 23, 2 one and 25. And we know that we already explored node zero and node three. So we ignore these two. We don't need to do any calculation for 220 and 223. So this one we ignore.

[00:26:07]But this one we can do calculation because one is are not explored yet. So here we calculate distance 2 + 4.

[00:26:17]Distance 2 is 9. 9 + 4 is 13.

[00:26:21]And we know that the shortest path so far was 14 and this one give us 13. So we update it. We update 14 with 13 and then update the predecessor also. We are reaching to one through two. So we add two in the predecessor array.

[00:26:40]Next is this one. We ignore this edge because see uh three is already explored. You don't need to check shortest part to three anymore.

[00:26:50]And next is 2 to5. So known this shortest distance to two already is 9. 9 + 3 will be 11.

[00:27:03]And 11 is less than 22. So we update shortest distance to five also. So it will be 12 and predecessor will be updated to two because we reach five through node two.

[00:27:18]So we explored uh um node two also one two three is already finished. We have three more node one node four node five. Again we search and see which one has the shortest distance between 13 infinity and 12. We choose this one. So we next we explore five. So we remove five from the v set and start exploring five. Five has a edge to three to two and to four. Three is already explored. Two is already explored. So we ignore these two edges. We just need to check and see if we can find a smaller distance uh going to four through node five.

[00:28:10]So this one we ignore. This one also we ignore. We just need to do calculation for this one. So distance 5 so far is 12. 12 to 8 is 20 and 20 is less than infinity. So we update for four. The distance now is 20 through node five. We update predecessor also.

[00:28:37]So we explore node five also.

[00:28:42]So 0 235 is finished. Between 1 and four the shortest distance is 4 1 which is 13. So next node that we need to explore is node one. Node one has three edges to zero to two and to four. Zero is already explored.

[00:29:03]Two is already explored. And we just need to check four.

[00:29:10]So this one ignore this one also ignore.

[00:29:13]This is the only one. This one is 13. 13 + 5 is 18 and 18 is less than 20. So we update with the shortest path that we find which is 18 and predecessor is one.

[00:29:34]So node one also finish. The last one is node four.

[00:29:39]It has two connection. One is already explored. Five also explore. So done. No update here. And this is the end result.

[00:29:50]The shortest distance between 0 to 1 is 13. 0 to2 is 9, 0 to 3 7, 0 to 4 18, and 0 to 512. And if you want to see the path, then you have to use the predecessor.

[00:30:08]Let's see how we use the path and then we will see another example.

[00:30:23]So here for example after you finish all if you want to say what is the shortest path between zero and four you start from four and have a look to the predecessor. So 4 to 1 and then from 1 to two and then two to zero. So from predecessor you find the path also 4 to 1 to two to zero is the shortest path and shortest distance also is in this array.

[00:30:55]Any question here?

[00:31:09]So last >> is there any path between two node?

[00:31:21]measures >> though that's uh you that is just showing if there any path between two them but that is just telling you is if there any path but we are looking for shortest path between so these are two different problem >> no that's that itself doesn't give you this result if you want to update it add some few thing that is not the original version. Maybe you can develop an algorithm based on that. But that one itself no don't give you this.

[00:31:58]That is just for unweighted and finding weight uh any path between them without um regardless of the weight.

[00:32:10]So let's see another example and then okay let's do this one because this one has direction also uh we want to suppose one is the source and we want to find the shortest path between 1 to 2 1 to 4 and 1 to 3 and our graph is also directed. So we have to consider this direction also when we are applying the extra algorithm.

[00:32:43]So let me skip it here.

[00:32:57]So first we need to initialize all the data structure that we need.

[00:33:03]One is this which shows I have to keep it like this.

[00:33:18]The distance shortest distance between them.

[00:33:28]Initially distance to one. Suppose one is our source is zero and the rest is infinity and then predecessor 1 2 3 4 which is minus one initially.

[00:33:58]Okay. Now we want to start from node zero. So node one. So start from one. So we have to see all the directed neighbor or nodes that have a connection with one.

[00:34:17]So we have connection between one to two sorry one to three with weight two. We have connection between one to four and one to two. Let's start with this one like 1 2 3 1 2 3 and weight is also two. So you have to calculate this one plus weight. So this one you already are on the source. So your distance to the source is zero plus the weight which is two. It will be two. Then you have to compare if the distance that you find to three is smaller than the distance you already have in the this array.

[00:35:09]Currently this 2 three is infinity. Now it's two. So you can update it. It will be two and you reach to three via node one. So you update this one also to one.

[00:35:25]So we already see this one. Next we want to explore this one. 1 2 4 and the weight is 10. Again this one plus weight this one is zero. The weight is 10. It will be overall 10. So the current this to four is infinity. And the weight that the distance that we found is 10. So we update it to the 10 and also predecessor to sorry one.

[00:36:04]One the next. Okay. This one also we see. And now this one one to two and the weight is six. This 1 + w 0 + the weight is six. So overall is six. So the current distance to two is infinity. We found six. So we updated to six and through node one.

[00:36:37]Any questions so far? So we processed node one. Now we have to choose two, three or four. Which one we want to do the next? Any question here?

[00:36:54]So which one I need to choose for the next round?

[00:37:00]>> Three. So now we have to process or explore the node tree because this one has the minimum. So let me put this and spread again here.

[00:37:16]So we update from here.

[00:37:20]One, two, three, four. This one is zero.

[00:37:26]This one is six. Two and 10.

[00:37:31]And the bread.

[00:37:41]1 2 3 4 is minus one one one okay now because the wine is already processed uh among two three and four three has the shortest distance so we choose three we want to explore node three now we have to check all the connection of three has connection to one has to two and to four. One is already explored. So we ignore this one. You don't need to calculate this one again because node one is already explored. So we have to just check 3 to two and 3 to 4.

[00:38:26]So let's start with 3 to two.

[00:38:31]3 to two is three. Okay.

[00:38:34]3 to two. And the weight is three.

[00:38:37]Correct? Or three or two?

[00:38:40]3 to two three. Okay. Now we say this three plus weight. Distance to three already is two plus weight which is three is five.

[00:38:57]Okay. If five is less than two. No. So we don't update it because this is larger than two. So no update here.

[00:39:11]Next is 3 to four and weight is 8.

[00:39:18]3 to 4 and weight is 8. So distance 3 + w distance 3 is 2 + 8 is 10. So we check four.

[00:39:34]Oh this one was to two. We should compare with this one. Yeah. So why you not saying anything?

[00:39:45]You have to compare it with five is less than six. So this will be five and then we reach through node three. Okay, it is 12. We compare it with node 4 already is 10. This is 12.

[00:40:04]So 12 is more than 10. No updates. So we explore node three also.

[00:40:10]Node three finished. So we already did node one. We already did node three. Now we have to choose between two and four.

[00:40:18]2 is five and four is 10. So next note that we explore is two.

[00:40:28]So distance 1 2 3 4 0 5 2 10. And the distance and the bread is - one 3 one one. So next we are exploring node two. Let's see the connection of node two. Two has just one outgoing edge which is to four and four is not an explorer. So we have to check this one. 2 to 4 and the weight is four.

[00:41:21]So 2 to four and weight is four. So this two plus weight. This two already is five and the weight is four which is nine and nine is a smaller than the current one. So we update it to nine and update the one to two. So the last is for itself. I think node four.

[00:42:04]Four has a connection to two and two is already explored. So this finished. This is the final result.

[00:42:12]This is the final result. This is the final distance array 0529. And this is the predecessor min -1 312.

[00:42:21]Any question?

[00:42:26]Just here because we have a direction we have to check the direction and then select the edges that uh actually have outgoing direction from a node that we are processing.

[00:42:46]Do you need more example or is clear?

[00:42:54]Yes or no?

[00:42:59]No question.

[00:43:02]You want me to do this one or is okay?

[00:43:04]>> Yes.

[00:43:05]>> Okay.

[00:43:14]So let's do this one.

[00:43:18]So the graph can be directed or undirected but it's weighted and weights are all non- negative. And here suppose the source is zero. And we want to find shortest distance between 0 to 1 2 3 and four.

[00:43:36]Again we have distance 0 1 2 3 4 because zero is a source. So distance is zero. The rest is infinity and then predecessor for all of them initially minus one.

[00:44:16]Okay, we start from zero node zero.

[00:44:23]So zero has edge to one and two. First let's check this one. 0 to 1 and the weight is four. So this 0 + weight 0 + 4 is four. So already the distance to one was infinity. Now we found four. So we update it. and then minus one will change to zero. Next is 0 to 2 and weight is 8.

[00:45:03]So this 0 + w this 0 is zero and the weight is 8. So overall eight. So distance to two we update it to 8 and this one zero. Now we already process node zero. Finish. Now we have to choose which node we want to do next.

[00:45:31]Which one I choose?

[00:45:35]Which one I need to choose for the next >> one.

[00:45:38]>> One. Because one the distance is four.

[00:45:42]two is eight and the rest infinity. So a smaller one is a four. So next node that you need to process is one. So next is node one.

[00:45:57]So let me quickly put this and zero 1 2 3 4 0 4 8 infinity infinity at and print 0 1 2 3 4 is -1 0 0 - one - one. So we have to check node one. So check the connection of one. One has a edge to zero to two and four. Zero is already processed. We finished the zero. So we ignore this one. We don't need to do any calculation here. So we have to check one to two and one to four. One to two is three.

[00:47:00]1 2 wait three. So this 1 + w this one is four.

[00:47:11]W is three 7. So note two already is was eight. Now we found a shortest spot which is seven.

[00:47:21]So we update it.

[00:47:25]We replace it with seven and predecessor will be true node one.

[00:47:33]The next was 1 to two. We already check 1 to 4 6 1 to 4.

[00:47:48]1 2 4 6. So this 1 + w this one is 4 + w 6 10. So let's check four. Four was infinity. Now we found 10. So we update.

[00:48:07]We put 10 here. True node one. So this one also finished. We already check node zero and node one. Now which one I have to choose?

[00:48:23]Which one I have to check next?

[00:48:55]Okay. Which one?

[00:48:59]Zero already done. One already done.

[00:49:03]Among two, three and four. This is seven. This is eight. This is 10.

[00:49:08]I have to process node two.

[00:49:15]So next we check node two.

[00:49:23]Okay, node two has a connection to zero which is already processed. So we ignore this one. 2 to one already process.

[00:49:30]Ignore this one. So 2 to three wait two.

[00:49:38]two to three weight two.

[00:49:43]So this two plus weight this two already is seven.

[00:49:50]The weight is 2 9. So we check three.

[00:49:54]Three was eight and now we found nine.

[00:49:57]So no update because this is larger than the previous distance that we already calculated. So note two also finish no update.

[00:50:09]Now between three and four three has the shortest distance. So next is node three.

[00:50:21]Three has a edge to two. Two is already processed. So we ignore this one. We have to check this one. 3 to 4 10 3 to 4 and weight is 10. So this three plus weight this three is 8 weightight is 10 is 18.

[00:50:47]So the current way distance to four is 10 and this one is 18. So no update. So node three also finished.

[00:50:57]And the last is node four. Last always we don't do anything because four has a connection to one already processed. Three already processed. So this is the final result.

[00:51:11]This one 0 4 7 8 10 and minus one 0 1 3.

[00:51:21]Oh previous time I updated I have to put it here. When we put eight, we have to update it to two.

[00:51:29]You can see better there. Why you not telling me we have to put two here, two here and yes, done.

[00:51:40]Because whenever we update the distance, we have to update the predecessor also.

[00:51:45]We reach to uh this node. So we have to update we reach it through zero. So this is zero.

[00:51:57]We reach two through node zero.

[00:52:01]Oh, where is it?

[00:52:04]Where is it?

[00:52:08]Oh, this eight was for two. Okay. No, this is this one. And what is this? Oh, this is infinity. Oh, we update it here.

[00:52:18]Yes, correct. This is two. It was here.

[00:52:21]Yes. Two. Yeah. Done. So this is the final distance 0 4 7 8 10 and the produces are min - 1 01 2 1.

[00:52:37]Any question?

[00:53:01]So if in the question they ask you how to find shortest path between two other vertx then you have to rerun this algorithm again because this one always find the shortest path between source and any other vertx. So if the source change you have to run all this algorithm again and recalculate all the distance and path and the next thing is uh uh the data structure that you use to save the vertics and then choose between them can be visited array can be a list or priority Q that we will discuss.

[00:53:48]us in week eight next week. Based on which uh data structure you use to save vertx the complexity of whole model can be different. So let's see how it affect the final result because every time we choose one of the vertx from the vertx set and then we process that vertx. So based on how you save those u list of vertx it can affect the final complexity. For example, if you use visited array that we use for DFS and um BFS. So it can be true or false. So if a node is already processed, we change the uh actually uh the value to true. For example, if already you process node zero, then you put true here in visited.

[00:54:43]It means you already processed the this node and you have to choose between the nodes that already not processed for the next uh round of the Dextra.

[00:54:56]So because you have V node the complexity be OV because every time you have to check all these and choose the one that is already false and has a minimum distance also. So if you use visited array the complexity of choosing which node is the next will be o v.

[00:55:17]If you use list also again the same for example initially your list say bcd and then you choose c as a next then your next round your unprocessed list will be b d. So again you have to choose and check uh among the node that already not processed which one has the smaller distance and pick that one. So even if you use list it will you have to check one by one is like a unsorted array or unsorted list that you have to every time uh search from first of item in the list and check which one has a smallest distance and pick that one as a next uh actually a note or you can use priority Q that we will discuss uh in week nine.

[00:56:12]In this case that we will see how it works. Then uh it will reduce the complexity because in priority uh Q uh we insert based on the priority. For example, here the priority is with the one has a smallest distance. It will uh decrease the complexity to log N. But we will discuss in week nine how actually priority Q work.

[00:56:42]So overall the complexity of dystra we every time we have to consider each edge. So the complexity the first stage is OE because we uh check each edge that connected to the current node in the worst case it can be OE and then we have a loop in each round we will choose uh the one node that has a shortest distance. So then inside of the loop each time we uh choose a node with the shortest distance. So overall the complexity will be E + square V. If you use list or array again will be E + square V or if you use priority Q then it will be um the choosing the item will be log V.

[00:57:35]So overall the cost will be OE plus V log V. So I can maybe show you better on the code itself.

[00:57:47]Where is Yeah, here.

[00:57:52]So this is how you this is the uh the loop that um your loop is based on the number of vertex that you have. As long as there is a vertex in the visited array, this uh line will be repeat and each time you have to find one node with the shortest distance. So this loop itself uh is v and then searching to find the one has a shortest distance based on which uh data structure you use to implement the v set. Then it can be OV or it can be log N and give you the final complexity.

[00:58:38]The only difference is what data structure you are using to save uh the V set.

[00:58:48]Uh we have some other version we do not discuss in this course. One is Floyd Marshall which can be used for negative weights also and also Bellman Ford another algorithm that also can be used for negative weights but Dextra itself uh applicable if you have just positive weights that's it this is about dystra to find shortest path uh for single source node in a graph.

[00:59:27]Any question about Dystra?

[00:59:42]Okay, maybe you can have 5 minutes break and then we start other topic.

[01:00:06]Yes.

[01:00:08]>> Yes. One moment.

[01:00:10]>> I want to put this Okay, they just asked one good question.

[01:07:55]If uh there are two or three nodes with the same distance, just choose one of them arbitrarily because always I say choose the one that has a smallest distance as a next note to process. If there is two or multiple nodes that already have similar shortest distance, just choose one of them. There is no difference on the final result.

[01:08:20]Okay.

[01:08:23]Uh next is minimum spanning tree. We already discussed about this spanning tree of a graph. A spanning tree of a graph is a tree that has all the nodes of the graph but subset of the edges of that graph. So that subset of the edges that you choose you should choose such a way that it doesn't create a cycle. This is what we know from previous uh sessions. Now we want to find minimum spanning tree. So in case our graph is weighted and then we want to create spanning tree how we should choose the minimum spanning tree. So a spanning tree that has a overall minimum cost.

[01:09:14]We have two algorithm for this. We have many but these two we will check uh discuss today cross call and p quite simple.

[01:09:26]So we already know that for undirected graph uh to create a spanning tree we choose all the vertex and a subset of edges. We have two condition.

[01:09:41]Uh first there is no cycle in a spanning tree and second between each pair of the nodes you have to have a path. So they should be connected or reachable. But what if we have a weighted graph? In weighted graph your spanning tree also need to be we are looking for minimum spanning tree. So the overall if you sum all the weights overall data spanning tree should be minimum also with minimum cost or minimum weight. For example if this is your graph both of them are a spanning tree because as you can see we include all the edges all the vertics and we choose a subset of edges they are all connected. It means if you choose any pair of the nodes there is a path between them and there is no cycle. Here you can see this both condition apply and here both condition apply. But this one is minimum spanning tree because if you sum all these numbers or cost 2 4 6 7 8 9 the total cost of this spanning tree is nine and this one is 11. So both are a spanning tree but this one is minimum spanning tree and today we want to use those two algorithm crosscall and p to see how we can find minimum spanning tree of a graph a weighted graph and one important things is each graph can have multiple spanning tree or multiple simple minimum spanning tree. So their their shape can be different uh but the minimum spanning tree all of them have the overall same cost but their edges that you choose can be different. Especially if you have a graph with multiple age with the same weight then you may have different minimum spanning tree and all of them are correct.

[01:12:00]So this is again the cross call is the person who invented this algorithm.

[01:12:07]Let's start with crosscall. Quite simple process to create minimum spanning tree.

[01:12:13]We start with an empty graph. So we have a graph that has just nodes no edges.

[01:12:20]And then we will sort all the edges ascending based on their weight from the shortest smaller weight to the largest weight. And then every time we choose the edge with a smaller weight and add it to our graph. We continue as long as there is no it this adding this edge cannot uh doesn't create any cycle. And we continue until we add v minus one edge into the graph. V is the number of vertex in spanning tree. Always the number of edges is uh less than number of nodes.

[01:13:04]So let's see how it works.

[01:13:07]Uh suppose this is our graph and we want to find minimum minimum spanning tree.

[01:13:15]So I prefer to do it this way is easier. Then I will show you on the graph. First thing we create an empty graph.

[01:13:31]0 1 4 3 and two. No edges. Then you find the edge that has a minimum weight. You may have two, three, four edge with minimum weight. Just choose one of them. Here there is no edges with similar weight.

[01:13:53]But if you see edges with similar weight, just choose one of them random.

[01:13:59]So here this is the edge that has a minimum weight. So first I add this one.

[01:14:10]So which one is the next?

[01:14:16]this edge because it weight is two. I will check if I add this uh will it create a cycle or no? No, because steel is a sparse. So we add this one also. We continue until we add v minus one edge into the graph. So we have five vertics. So we need four edges. What is the next?

[01:14:48]Which one I have to choose next?

[01:14:51]0 to three.

[01:14:56]We added because it doesn't create a cycle and also still we have space to get more edges. What is the next?

[01:15:06]Which one has the smallest weight?

[01:15:15]0 to can I add 0 to four?

[01:15:20]>> No. Because it create cycle. So no. What is the next?

[01:15:28]We cannot select this one also because if I add this one again it will create cycle. So this one also. No. Next three to two done finish. Because we have a five vertex we can maximum add four edges no cycle and also there is a path between every pair of the nodes. So this is correct.

[01:15:57]This is the minimum spanning tree of this graph. So we started from empty graph then we start adding edges in ascending order. We add v minus one edges and every time we have to check is there if it create cycle or not. If it create cycle we ignore it and then check the next one.

[01:16:19]So this is the final minimum spanning tree.

[01:16:24]Any question?

[01:16:27]So let's see in the slide. So started from here we add this one and then this one and then this one.

[01:16:39]Four we cannot add five we cannot add and then six. So this is the final result.

[01:16:54]So this is the final minimum spanning tree of this graph.

[01:17:01]So as you can see this is the pseudo code.

[01:17:04]Input is a graph. Output is minimum spanning tree. Start with a empty graph which has all the vertex.

[01:17:15]And then we sort all the edges ascendingly based based on the weight.

[01:17:20]And for each edge we add to the MSD and then check if it is create cycle we remove it and we continue until we have V minus one edges in the minimum spanning tree.

[01:17:35]This is what we did and we can have another version. One is checking if it create a cycle or another version is again we'll start from empty graph. We sorted all the edges and then we when we want to add one edge to our MSD we will check if if there is a path already between V and W we do not add that edge. So for example this one we ignore 0 to 4 because already there is a path between 0 to four. We do not add this edge. So instead of checking cycle it says checking cycle is if I add this edges and then check if there is a cycle. But the second algorithm do not add the edge. Just check if there is a path between the source and the destination.

[01:18:37]If already there is a path you do not add this edge at all because it will create a cycle. So do two different perspective but the uh outcome the results are the same. The first one we add and then check if create a cycle. If it's create we remove it. Second one we do not add. We first check if there is a path between the first and second node.

[01:19:02]If there is a path we do not add. Any question.

[01:19:14]So uh this is a proof on saying that there is no any algorithm that can find a minimum spanning tree with uh overall weight less than what crossall can find. So if crosscall find a minimum spanning tree this is real the minimum one that can be find this guarantee that there is no any other spanning tree with overall weight less than what kal already find for us.

[01:19:49]So this is just a proof. Um I quickly go through that how we can prove that uh that minimum spanning tree by crosscall is actually minimum and it's guaranteed that there is no better algorithm than corros to find minimum spanning tree.

[01:20:09]Suppose we have a graph and K is the tree that we generated using crall algorithm and A is another one that generated using another algorithm and both of them are minimum spanning tree. Then we will check the tree that already created by cross call algorithm and we find if there any edge that exist in cross al spanning tree but is not exist in the other one that generated by another algorithm and then add that edge to the spanning tree and then remove the highest weight age. We will see in the example and then at the end we will see that with doing repeating this process the second tree will be like the cross skull tree.

[01:21:11]Just imagine here this is the graph and this is all the edges in this graph and this one two three are weight of the edge. This is the graph and then this is the minimum spanning tree that crossall algorithm find. So in crossall it find that this if you include these edges it will give you the minimum spanning tree and this is a minimum spanning tree through another algorithm.

[01:21:44]So first we find one edge that appeared in corrosol but is not in the other spanning tree. So here this one so it is more large this graph. So as you can see there is three dots. So it's a larger just a part of a graph. So we found one uh edge that is appeared in cross call but is not appear in the second minimum spanning tree. We find this edge E5 is here.

[01:22:13]So we add it in the tree that generated through the other spanning tree algorithm we add. And now we can see that there is a cycle here. And if you check here, this edge is E4, E5, E1, and E8. First, we add this edge here. And then we remove the edge that has the highest weight. So in this E8 has the highest edge. So we remove it.

[01:22:45]So it will be like this. As you can see if you continue this process you can see that this tree will be more look like cross call tree to original minimum spanning tree that generated but the other algorithm. See here this was the tree that generated by cross call.

[01:23:06]This one is was generated with other spanning tree with adding the edge and removing the one that has a highest weight. We can see that this second tree also look like the cros tree. So it's proved that and if it continue more and more it will be identical with corrosol one. So it shows that there is no uh minimum spanning tree algorithm that can find a minimum spanning tree with lower cost of crosscut and complexity.

[01:23:45]Initially we need to sort all the edges.

[01:23:49]uh for example if you merge sort or quick sort in an average or hip sort will give you e log e hip sort you will see in week nine. So sorting minimum cost is e log e this is the first thing is a fixed because you always need to sort all the edges and then choose the one with minimum weight.

[01:24:13]So this part is e log e and then we have a main loop. That main loop uh actually run e times and e is the number of edges and every time we need to check if adding this edge create a cycle or not.

[01:24:31]So for example if we use DFS to check if there is a cycle or not or whatever algorithm we are using it is affect the final complexity of this model because every time you add a edge and then check if there is a um cycle or not. Imagine we are using DFS then the complexity of finding cycle will be O V.

[01:24:57]Why it is OV? It is not V + E you think because the complexity of DFS is actually V + E remember because this is a spanning tree and number of edges is always less than number of nodes and because in big O always we take the dominant part so we can ignore E here because E is always smaller than V.

[01:25:37]So the total cost will be E log E which is for sorting edge and then main loop which is E mult* V. So overall we get the most dominant part which is O E multiply V. So this is the overall complexity of crosscall algorithm.

[01:26:02]If you consider corrosol algorithm uh we have another way to reduce this and make it uh more simple to reduce the complexity.

[01:26:23]Uh another way that we do not discuss in detail is using uh union find instead of cycle check. In this case we suppose that we have a connected component and if the node that you choose are from same connected component we do not add the edges because it will create a cycle. So this is per this different way of checking if there is a cycle or not.

[01:26:52]So every time it will check if these two node that you are selected and want to add the edge are in the same corrected connected component or not. So in this case the uh complexity is O alpha V which is inverse occurment function which is in worst case can be a constant number. So it can say the complexity can be O1.

[01:27:21]So in this case then the overall cost will be for sorting plus E because the cycle check now is constant. So it will be E log E plus E. If we choose the most dominant part complexity will be E log E that we can instead of E log E say E log V because we know that the number of edges always less than square V. So we can say log e is almost equal to log v. So we can say e log v as a final complexity of c call algorithm.

[01:28:02]Any question here? Just have a look to this number formula.

[01:28:22]Do you want another example for this algorithm or is he or you want to do another example?

[01:28:35]>> Yeah.

[01:28:36]>> Okay. So suppose this is the graph and we want to make minimum spanning tree of it. So let's see if I can do here or Yeah.

[01:28:56]No. Where is it? No. Here zero.

[01:29:06]One.

[01:29:09]2 3 8 7 6 5 and 4 5 6 7 8 9. So we have nine vertics. So we need eight edges.

[01:29:40]One, two, three, four, five, six, seven, eight, nine. Okay, we start from the cheapest one. The lowest weight.

[01:29:49]Which one has the lowest weight?

[01:29:52]This one. Seven to six. So I add this one here.

[01:29:58]One. Now I need seven more.

[01:30:02]So when which one is the next?

[01:30:06]We have 6 to5 with cost 2 and 8 to two with cost two. You can choose whatever you want. This one or that one. No difference. So let's choose this one.

[01:30:24]Two.

[01:30:25]We need six more. What is the next?

[01:30:30]is this one because it's not creating cycle I'm just adding so I need five more which one is the next 0 to one is option two to five is also option so let's get this one four we have four we need four more I can choose this one also because this is a minimum again compared to rest and it doesn't create a cycle. So I can add this one also four. I need three more.

[01:31:13]Okay, we use this one also.

[01:31:16]Now this is 10. This is 14. This is 9. 7 6 7 8. So this is the shortest smallest one. So can I add this one?

[01:31:26]>> No.

[01:31:27]>> No. Because this is create cycle. Next smallest one. This 7 to 8. Can I add?

[01:31:37]>> No. Because it creates cycle. Next is 2 to three. Can I add? Yes. Because it doesn't create cycle. So I need two more. What is the next minimum?

[01:31:52]We have eight here and eight here.

[01:31:56]Can I add this one?

[01:32:02]It doesn't create.

[01:32:04]Can I add this one? No.

[01:32:09]Uh, next is this one. Can I add this one?

[01:32:15]Done. Finished.

[01:32:18]Because I add one, two, three, four, five, six, seven, eight edges. the and you can see there is no cycle and there is a path between any pair of the nodes.

[01:32:31]So this is the minimum spanning tree of this graph.

[01:32:40]As I said mi based on for example uh you if you have a equal edges with equal weight based on you choose which one you may see that final tree has a different shape but the cost is still minimum. So doesn't matter maybe two of you try this but one of you choose this one first and another choose this one first. So final three the shape can be different but the weight both of them will be the same and both of them will be minimum spanning tree.

[01:33:23]Any question?

[01:33:25]So let's see prim also how prim find the minimum spanning tree.

[01:33:39]So p is developed by these two people yarn and p.

[01:33:48]The first one is developed and the second one rediscover it again.

[01:33:55]But is based on the second one name interesting. Okay. Uh p also find minimum spanning tree here also we but the approach is different uh start with an empty graph.

[01:34:15]So when I say empty graph even not any node starting point then we start from any vertex we have to choose one vertex and a start uh from that vertex that can be any vertx random you choose one vertx and then build your u msd start from that vertex. We just get one vertex and add it to our MTMS MST and then we find the cheapest edge that is connected to this vertex and any other vertex. The condition is when you choose a edge one side should be connected to the vertex that are already in MSD and one side should be a vertex is not in MSD yet and it should have the lowest cost also. So there is two condition here. You first choose a vertex. Then you need to choose a edge.

[01:35:14]That edge one side of it should be in the MSD. One side of it shouldn't be in the MSD and it has a minimum weight.

[01:35:24]And then you choose and continue until you add V minus one edges in your minimum spanning TD and again no cycle.

[01:35:36]low see what does it mean?

[01:35:40]Uh okay here if I want to be like what we explained the first stage minimum spanning tree nothing now I will choose one vertx for example we choose zero then we choose we check all the edges then one side is select is connected to zero and one side is connected to the nodes that are not in the minimum spanning tree yet. So it means this one, this one and this one. So with among these three which one has the minimum weight zero to one. So we expand our MSD now will be zero and one and weight one. So we creating this MSD gradually. But in chorus we already have all the notes and add edge. But here the approach is different. Now this is important here.

[01:36:45]Let me change the color.

[01:36:49]Already in MSD we have zero and one. Now we want to check all the edges. Then one side is connected to zero or one and other side is a node that is not in MST yet.

[01:37:05]So which edges I need to check now?

[01:37:10]I can check this one because one side is connected to zero and one side is connected to the node that is not in MST yet. I can check this one because one side is connected zero and one side is not connected to the is not in MST. Next is this one.

[01:37:30]One side is connected to one and one side is a node that is not in MST and next is this one. Now among these four which one is minimum 0 to three.

[01:37:51]Now which edge I need to check?

[01:37:55]Now I have 0 1 and three in the MST.

[01:38:02]Four and two are not in the MST. So I should find the edges. Then one side is connected to zero, one or three and other side is four or two. So which one?

[01:38:19]It can be this one again.

[01:38:23]Correct? because one is connected to zero and one is four.

[01:38:28]Next can be this one again because one side is connected to one, one side is to four. It can be this one again.

[01:38:38]One is connected one, one is to two.

[01:38:42]It can be three to four also. It can be three to two also. Now among them which one is the smallest one?

[01:38:52]This one sorry like this. Now again we have to find edges that one side is either connected to 0 3 4 1 and other side is two.

[01:39:16]So which which one is the next with this one six. So this will be the end because already 2 4 5 I selected four edges. Uh there is a path between any pair of them and there is no way to add more. So this is our spanning tree.

[01:39:46]So now look at here. First we add zero.

[01:39:51]So we have three options. One, four or three. Among these three, one is the smallest one. So we choose this one.

[01:40:04]Now we have four options. This one, this one, this one, this one. on one side is connected to the nodes that are in the uh MST and other side are not in the MSD. Between these four again I have to choose the smallest one which is this one.

[01:40:27]Then I have more options. This one, this one, this one. This one and this one.

[01:40:31]Again we choose this one.

[01:40:35]And then the last one we choose this one and done.

[01:40:44]This is this will be the final result.

[01:40:50]This is how prime works.

[01:40:58]So start from empty graph and then this uh among the edges in the graph we have to choose the edge that one side is in the MST one side is not in MST and then we check uh every time that we choose one we have to check if Um we we already choose the vertx. Now we have to find the cheapest edge among all the edges that are possible to be choosed. And we select the cheapest one. Add that one to our MSD.

[01:41:39]And we can use one another data structure that tell us which edge already being used and which edge is remaining. So this one actually save the edges that already being added to our MSD and and every time we add it to the MSD we should remove it from that used edge that edges that one side is connected from connected to the MSD and connected one side is not connected to MSD.

[01:42:12]So we have to consider every edge and then our loop is based on number of nodes that we have. Then when you we choose a node then we have to uh find the cheapest edge connected to that node um which is OE because just imagine that edges are in unsorted array. So you have to check one by one to find the cheapest or the one with the minimum weight. So overall cost OE is um to find one edge is connected to um MSD and one is not connected to MSD and our loop is V multiply E that E is the edge with the minimum weight. So overall will be E plus V E and then more dominant part is V E.

[01:43:13]We can make it better with Fibonacci heap that will be in the week 9 in this case then it will be E + V log V instead of E. So it can be cheaper.

[01:43:30]It depends on which data structure we are using to find uh the minimum weighted edge.

[01:43:39]But the current sudo code is ov multiply e that what we see now.

[01:43:53]Okay. Do you want to do again for frame also quickly?

[01:43:58]This is quite large but too much option.

[01:44:03]Okay, let's do at least few part of it or okay I can do on this. So suppose I want to apply p you help me. Suppose we start we choose a because if I draw it again it will be too much. Now what are the options?

[01:44:30]I started with A and I want to use P and find the minimum spanning tree.

[01:44:37]What are the candidate edge here?

[01:44:51]A to B, A to C and A to D. These three are candidate edges here. So the one that has a minimum weight is A to C. So we choose this one.

[01:45:06]So already our MSD has two nodes and one edge. Now we have to check another candidate set of candidate. So four.

[01:45:19]So you have to have a look to this one to this one. No, sorry. Uh not this one. So we have to one is this, one is this, one is this one, one is this one, one is this one, and this one. These are the edges that one side is connected to A or C and other side is some other nodes. So among these six candidate we have to choose the one that has the lowest weight.

[01:45:59]This is four. This is two. 7 5 11 8. So this one has the lowest weight. So we choose this one.

[01:46:15]Now our MSD has A C B edge A to C and edge B to C.

[01:46:26]Then we need to check all the other candidate. This one cannot be is because if I consider this one make cycle. So this is the option.

[01:46:42]This can be option. This can be option.

[01:46:45]This is again option. And this is again option.

[01:46:50]6 8 11 5 and 7. So this is the smallest one. So we need to proceed like this. Every time we see uh find the all the candidate age, one side is connected to MSD, one side is not connected to MSD and then choose which one has the minimum weight and add that one to our MSD.

[01:47:20]And then we continue like this. Any question.

[01:47:28]Okay, that's it.

[01:47:38]And I think I'm not sure. Let's check if assignment two is already published. Assignment.

[01:47:53]Yes.

[01:47:56]Okay.

[01:47:58]this assignment to also you can have a look maybe we can quickly go through next Tuesday and explain how it works.

[01:48:13]Okay, thank you.