Dijkstras Shortest Path Algorithm Explained | With Example | Graph Theory

hey everyone and welcome to this video on dijkstra's shortest path algorithm suppose you have a graph connected by weighted edges like this one then dijkstra's algorithm allows you to calculate the shortest path from a fixed node to every other node this can be applied for example in digital mappings so suppose those nodes are cities and the edges are routes between them then dijkstra's algorithm will allow you to calculate the distance from one city to every other city let's take a closer look at this graph and suppose we want to calculate the shortest distance from a

to every other node in this graph this can be easily done with dijkstra we just have to keep track of some information while iterating through this algorithm the first information we need to keep track of is which nodes we have not visited yet so in the first step we mark all nodes as unvisited so therefore we create two lists a list of unvisited nodes that contains every node in the graph and also visited nodes that is empty in the beginning in the second step we assign to all nodes a tentative distance value that will be

changed over time so therefore we can use this table on the right which consists of three columns in the first column we have the node in the second column we have the current shortest distance from a to this node so in the beginning of this algorithm we know nothing of any distances to any other node then a so we set a to zero because the distance from a to a is zero and every other distance we set to infinity and in the last column we store the previous node that leads us to the shortest distance

and this column will be empty in the beginning because currently we have no information about this so those are the things we need to keep track of and now we can start with the first iteration since we start at node a we start by calculating the distance to all unvisited neighbors of a the distance from a to b is 2 and the distance from a to d is 8. and now we can update our table on the right if we have found a new shorter distance to one of the unvisited nodes so b and d

are unvisited and the current distance is infinity so we can update the distance from a to b to 2 and store a as the previous node in our table and the same applies to the node d we can update the shortest distance to d to the value of 8 and with the previous node a and now our iteration ends here and we can mark a as visited remove it from our unvisited nodes and put it in our visited nodes list the last step we didn't talk about yet is to pick a new node as a

current node to explore this graph further and therefore we always choose note with the current minimal distance in all our unvisited nodes so when you look at our table we have a with a distance of 0 but a is already visited we have b as an unvisited node with a distance of 2 and we have d with a distance of 8 all the other nodes have distance infinity so b has the current shortest distance of all unvisited nodes this means that b becomes our current node for our node b we can now go back to

our step 3 to calculate the distance of all unvisited neighbors of b so unvisited neighbors of b are e and d and the distance calculation works as follows since b has a current distance of 2 we need to add this 2 to the weight of the edges to e and d so now let's first look at the node e node e will have the current distance 8 from a over b and now we need to check if a8 is less than the current shortest distance that we stored in our table and the current shortest distance

we sort in our table is infinity and 8 is certainly less than infinity so we update our shortest distance to e and set b as a previous node now let's look at the node d d will now have a distance of 7 2 plus 5 from a over b this means we need to compare this 7 to our current value 8 in the table and since 7 is less than 8 we set the current value for the shortest distance to 7 and we set the previous node to b now we are finished with b because

we visited all unvisited neighbors of b and we can mark b itself as visited in the next step we choose a new current node from all unvisited nodes again and we choose the node with the minimal distance the node with the minimum distance in this case is d because it has a distance of seven we now calculate the distance to all unvisited neighbors of d and in this case we need to add seven to this distance because currently the shortest distance from a to d is seven when we look at our table so now we

need to consider if we need to update the distance to e or we need to update the distance to f so let's start with e the distance from a to e over d is ten seven plus three but ten is not less than our current distance eight that we have stored in our table so we won't update our distance to e when we look at the node f on the other hand the current distance we have in our table is infinity but now we get a distance of 9 from a to f over the node

d so we update our shortest distance in the row f set it to 9 and set the previous note to d we can now mark d as visited and we can go on with the next note in the unvisited note lists with the current minimal distance and this will be e because e has a distance of 8 and f has a distance of 9 and c of infinity so we calculate the distance from e to c and e to f in this case we need to get at 8 to the distance because 8 is the

current distance from a to e let's start with the node c we now have a distance of 17 from a to c over the node e and this is certainly less than infinity so we can update our distance to c in our table set the shortest distance to 17 and the previous note to e when we now look at f we see that we have a new distance of 9 to f which is exact exactly the same as our old distance to f so we don't update anything and we are finished with our node e

now we have f and c left as unvisited nodes and f has a distance of 9 and c has a distance of 17. we always start with the one with the minimal distance so we start with f and the only unvisited neighbor is c and now we see that we have a distance of 12 from a to c if we go over the node f so we can update the shortest distance to c212 set the previous node as f and mark f as visited this leaves us with node c since c has no unvisited neighbors

we're done here and we can mark c as finished and now we're done with the algorithm and in our table we have some important information about this graph we have now the shortest distance from a to every other node in this graph and we have the previous node which helps us to reconstruct the shortest path so for example if we want to reconstruct the path from a to c the first thing we see is that the shortest distance is 12. to find the shortest path now we start at the node c look at this at

its previous node which is f in the table so we mark this node from f to c and now we look at f and see that it has the previous node d so we marked this edge from d to f we now just need to look at the node d in our table we see that it has the previous node b so we mark the edge from b to d and when we look at the node b in our table we see that it has the previous node a and now we have found a connection

from a to c that has the length 12 and is the shortest path i hope this video helped you to understand the dijkstra algorithm if so please leave a like and subscribe for more computer science and programming videos