Dijkstra’s Algorithm in an Undirected Graph

In 1956, Edsger Dijkstra was shopping with his fiancée in Amsterdam, and sat down to have a cup of coffee. While sitting there, in twenty minutes, he designed the algorithm he is most famous for (and is named after him): Dijkstra’s algorithm. The algorithm finds the shortest path between a node and all other nodes in a graph with weighted edges. The greatest thing about it is how simple and efficient it is: there are only 6 steps, and no one has found a more efficient method to solve the shortest path problem.

Step 1

We start with a graph with weighted edges. This graph can either be directed, which means edges between nodes can run in one or both directions, or undirected in which edges always run in both directions. Here we will use an undirected graph:

A nice undirected graph.

In this example, we will be moving from Node 0 to all other nodes. First, we initialize a set that keeps track of visited vertices in the graph. This will initially be empty, and represented by visited = {}.

Step 2

Add initial values another set that keeps track of distance to the origin node. The index will represent the number of the vertex. The source node should be set to zero, and all of the others as infinite. In our example, this set will be nodeDis = {0, INF, INF, INF, INF}.

Step 3

Pick the node with the lowest distance value, and check to see if that node is listed in the visited nodes list (at first our visited nodes set will be empty). If it is not, visit that node. If it has been visited go up the distance values until one is found that has not been visited. Our first visit will be Node 0:

Node 0 is being visited.

Step 4

Add the selected node to the visited set. Our visited set is now {0}.

Step 5

We now update the length of each node connected to the selected node in our nodeDis set. The distance is equal to the sum of the edge between the edge to the selected node, and the distance of the selected node to the origin node. If the distance is less than the distance listed in the target node’s distance, it is replaced. The nodes connected to Node 0 are Node 1, Node 3, and Node 4:

Node 1, Node 3 and Node 4 are connected to Node 0.

nodeDis now {0, 3, INF, 8, 7}.

Step 6

This last step is actually multiple steps. Repeat steps 3, 4, and 5 until all nodes have been visited. This plays out like this:

Node 1 is selected : visited = {0, 1} : nodeDis = {0, 3, 4, 7, 7}

Note that 3 has been visited before but distance between Node 0 and Node 3 directly is more than the distance between Node 0 to Node 1, then Node 1 to Node 3, and so the distance logged changes from 8 to 7.

Node 2 is selected : visited = {0, 1, 2} : nodeDis = {0, 3, 4, 6, 7}

Node 3 is updated once again! The distance from Node 0 to Node 2 to Node 3 is less than the distance from Node 0 to Node 1 to Node 3, and so the distance is updated again to 6.

Node 3 is selected : visited = {0, 1, 2, 3} : nodeDis = {0, 3, 4, 6, 7}

No nodes are updated; the distances from Node 3 to Node 4 or Node 1 are greater than previously established distances.

Node 4 is selected : visited = {0, 1, 2, 3, 4} : nodeDis = {0, 3, 4, 6, 7}

Again, no nodes are updated, as all distances from 4 are greater than previously established.

Tada!

All nodes have been visited so the algorithm is finished! The shortest path to any node from Node 0 can be found by following the path in teal. This can be used for any graph with weighted edges.