Dijkstra's Algorithm

Tags

algorithm

Is an algorithm to find the shortest path from a given start node to every other node in a graph.

Formulation

Ordinarily the algorithm works by defining a box containing three sub-boxes over each node. \tikz \draw (0,0) rectangle (2,1) (1,1) -- (1, 0.5) (0, 0.5) -- (2, 0.5); The top left box contains the order of labelling, as in the iteration index at which we finalised a path from to this vertex. The top right box contains the final total weight to reach this vertex from the start node (filled in alongside the top left box). The wide bottom box is a space to place pending weight values. This is reduced as we fill in other possible edges and at each step we fill in the edge for to the node with the smallest value in this box.

The algorithm is as follows:

1. Label the start vertex 1 in the top left-hand box. Its distance is 0 from the start vertex so we put this in the top right box.
2. For each vertex directly connected to the start vertex, enter the distance from the start as a working-value in the bottom box.
3. Find the vertex with the smallest working-value and place the next-number (2) in its top left-hand box. The working value becomes the length of the shortest path from the start vertex to this vertex and is also placed in the top-right sub-box.
4. From the last labelled vertex (2) add the edge from this vertex to each vertex it's connected to and add it to the working value for that vertex. Note: Record whether it is smaller than the previous working value.
5. Find the next unlabelled vertex with the smallest working value, number it and label it.
6. Repeat steps 4 & 5 until the target vertex (the one you're trying to find) or all the vertices have been labelled.

You can discover the shortest path (series of vertices) from a target vertex to the start vertex by tracing backward from it in such a way that an edge is only included if its distance equals the change in label values.

TODO: Example.