Understanding Djikstra's algorithm

[Imagine]

So on CS final, there's most likely going to a question about writing Dijkstra's algorithm on it. I understand what it does, and what it looks like when its run, but I don't know is how to code it, and the purpose of every line of code in it.

Psuedo code given to me by my professor:



I literally have no clue what the purpose of every line of code. What does each line of code do, why does it need to be that way, and how would I implement it in actual code (more specially, how would I set previous to undefined?). What line of code should be at line 24?

[Torychu]

Hi Imagine,

So when you say you know what it does and how it looks like, I assume you know how to do it by hand using a table with vertices, previous node, and distances as columns. Let's go through the idea of the pseudo code section by section.

Lines 7-11 are just initializing those values in the "table." Distances will only be overwritten by a smaller value because you are looking for the shortest path from a vertex to every other. That is why the initial distances will be as big as possible as a dummy (infinity). Previous vertices will obviously be undefined. The starting vertex (s) will be initialized to 0 (the distance from a vertex to itself).

Lines 15-17 involve a priority queue. Specifically a min priority queue, if you're finding the shortest path. You need this PQ to operate on the next unvisited vertex with the smallest weight. This is just how Djikstra's algorithm works--by finding the shortest distance from every vertex to your starting vertex. Initially you add every vertex to the PQ, with the starting vertex at the top of your PQ because its weight is 0.

Lines 20-34 is the meat of the algorithm. It is popping the min (u) off the PQ in each iteration and updating the the distances and previous nodes of all of u's neighboring vertices. 21-22 is the popping part. Line 23 is a special case and might be difficult to understand if you're reading the code top-down in one iteration, so let's come back to this later. The FOR loop at 26-33 is looping through all of vertex u's neighbors. You need to update the distances of the origin to all of u's neighboring vertices by adding u's distance to the distance from u to the neighbor. In the next iteration, it will do the same thing starting with the neighbor with the smallest weight. So now let's go back to the IF statement at line 23. Because we're updating all neighboring vertices to proper values and overwriting the initial infinity, there couldn't be a case where distance[u] is still infinity, right? Wrong. What if there is a vertex that isn't a neighbor to any other vertex at all? A disconnected graph. Then the infinity won't be overwritten. Since this is a min PQ, the rest of the vertices will also be disconnected. In this case, you are done with your algorithm. Break.

Lines 38-42 is reconstructing the path from origin to destination using the "table" you just created. You start at the end and work your way backwards with the 'previous' value until you hit the origin.

I'm not sure what specific parts you have trouble implementing and in what language. But to answer your question about how to set previous to undefined, you can choose undefined to be whatever you want. Same goes with infinity. You can choose it to be -1 since distances can't be negative or the max value of your data type. However, once you pick something, you need to stick with it.

Hope this helped.