Dijkstra's Algorithm, in Simple Steps

Dijkstra’s Algorithm, published by Edsger Dijkstra in 1959, is a powerful method for finding shortest paths between vertices in a graph. This Instructable contains the steps of this algorithm, to assist you with following the algorithm on paper or implementing it in a program.

Note that the steps provided only record the shortest path lengths, and do not save the actual shortest paths along vertices. If knowledge of the composition of the paths is desired, steps 2 and 4 can be easily modified to save this data in another associative array: see Dijkstra’s 1959 paper in Numerische Mathematik for more information.

Alright, let's get started! In these instructions, we assume we have the following information:

• A graph G
• A set of vertices V
• A set of edges E (where each edge has a nonnegative weight)
• A starting point s ∈ V

Note that the "element of" symbol, ∈, indicates that the element on the left-hand side of the symbol is contained within the collection on the other side of the symbol. For example, s ∈ V indicates that s is an element of V -- in this case, this means that s is a vertex contained within the graph.

These directions are designed for use by an audience familiar with the basics of graph theory, set theory, and data structures. With this prerequisite knowledge, all notation and concepts used should be relatively simple for the audience.

For more information on the details of Dijkstra's Algorithm, the Wikipedia page on it is an excellent resource.

Construct a (now-empty) mutable associative array D, representing the total distances from s to every vertex in V. This means that D[v] should (at the conclusion of this algorithm) represent the distance from s to any v, so long as v ∈ V and at least one path exists from s to v.

Construct a (now-empty) set U, representing all unvisited vertices within G. We will populate U in the next step, and then iteratively remove vertices from it as we traverse the graph.

For every v ∈ V:

1. Set D[v] to infinity. An infinite distance in D for a given vertex indicates that no path has (yet) been found from the starting vertex (s) to v.
2. Add v to U, indicating that v is unvisited.

Set D[s] to 0. This renders s the vertex in the graph with the smallest D-value.

Note that in the below instructions, we repeat directions as we iterate through the graph.

If U is not empty (that is, there are still unvisited nodes left), select the vertex w ∈ W with the smallest D-value and continue to step 4. Otherwise, go to step 5.

Remove w from U.

Iteratively, for every adjacent vertex (neighbor) n of w such that n ∈ U, do the following:

1. Let a be equal to D[n] + weight(w, n), where weight(a, b) is the weight of the edge between two adjacent vertices a and b.
2. If a < D[n], then we have identified a shorter-than-previously-thought path to n. To store this information, set D[n] to a.

Go back to step 3.

The algorithm is finished. At this point, D is “complete”: for any v ∈ V, we have the exact shortest path length from s to v available at D[v]. If no paths exist at all from s to v, then we can tell easily, as D[v] will be equal to infinity.