Dijkstra's algorithm

Dijkstra's algorithm finds the length of an optimal path between two vertices in a graph. (Optimal can mean shortest or cheapest or fastest or optimal in some other sense: it depends on how you choose to label the edges of the graph.) The algorithm works as follows:

Choose the source vertex
Define a set S of vertices, and initialise it to emptyset. As the algorithm progresses, the set S will store those vertices to which a shortest path has been found.
Label the source vertex with 0, and insert it into S.
Consider each vertex not in S connected by an edge from the newly inserted vertex. Label the vertex not in S with the label of the newly inserted vertex + the length of the edge.
- But if the vertex not in S was already labelled, its new label will be min(label of newly inserted vertex + length of edge, old label)
Pick a vertex not in S with the smallest label, and add it to S.
Repeat from step 4, until the destination vertex is in S or there are no labelled vertices not in S.

If the destination is labelled, its label is the distance from source to destination. If it is not labelled, there is no path from the source to the destination.

Example

Suppose A is the source state. To explain the algorithm, we'll record the sequence of states we are in each time we get to step 4.

A has label 0. S = {A}.
A has label 0, B has 14, D has 22, E has 4. S={A,E}.
A is 0, B has label 14, D has been relabelled 16, F has 14. We inserted F (we could have chosen B instead). S={A,E,F}.
No change to labels. S={A,E,F,B}
Labels as before, and also G has 17. S={A,E,F,B,D}
No change to labels. S={A,E,F,B,D,G}
Stop because there are no labelled vertices not in S

The labels now record the shortest distance from A. (States with no label, such as C, cannot be reached from A.)

Dijkstra's algorithm calculates the length of the optimal path. But we can easily generalise it so that it can also give us the path itself. One way to do this is to maintain, along with the label for each node, the previous node we used to get there. Then the path can be extracted by starting at the destination and following the previous-node labels.

Programming the trains route finder

I suggest maintaining a tableau, perhaps stored as a hashmap, like in these examples. The label of a city is the earliest time we could reach that city. The tableau contains the cities we have labelled, and there is a boolean ("shortest?") which indicates whether that city is in S. The tableau also contains the previous node, to allow us to extract the shortest path, leg by leg, starting at the destination and working backwards. See my examples.

Page written by Mark Ryan
Page maintained by Mark Ryan
Last modified: 29 October 2004