Dijkstra's Algorithm

[darwinrlo]

To do

• Introduction: introduce what we're given and what the problem is
• Theory
• Time and space complexity
• Implementation
• Appendix: How to actually construct the paths
• Appendix: How to build an adjacency-list representation graph

[darwinrlo]

ALGORITHM

We are given a directed graph and a vertex from the graph. We are to compute for each vertex other than the vertex we were given the shortest distance to it from the given vertex along any path through the graph. We will call the vertex we were given the origin vertex.

To start off, assign a key to each vertex. For the origin vertex, the key is assigned to be 0. All other vertices are assigned a key of INF (for positive infinity).

Next, create an instance of a set that we will use to store vertices for which the key is equal to the shortest distance along any path to it from the origin vertex. We'll call this set the result set.

Then insert all vertices into a heap. A heap element consists of a key and a value. In this case, the key is the key of the vertex, assigned previously, and the value is the vertex itself.

Now everything is set up and we do the following until the heap is empty:

• Extract the minimum element from the heap. On the first loop iteration, this minimum element is simply the origin vertex.
  • Add the vertex corresponding to the heap element to the result set.
  • Update the keys for the newly finalized vertex's neighboring vertices that are still in the heap. These neighboring vertices are now in the frontier of the result set; that is, there are edges, called crossing edges, that originate from inside the result set and end at these vertices. Remove each such vertex from the heap, set its key to the shortest distance along any path from the origin vertex to it through a crossing edge that ends in it, and re-insert it into the heap.

Once the heap has been depleted, each vertex's key is now equal to the shortest distance along any path to it from the origin vertex.

[darwinrlo]

GOAL

We are given a directed graph and a vertex from that graph, which we will call the origin vertex. For each vertex v in the graph, we are to compute the shortest distance from the origin vertex to v, which we will denote MinDist[origin](v).

[darwinrlo]

APPROACH

Let's say we are somehow to construct the following situation.

Property 1: There is a set of vertices from the input graph, which we will call Finalized, for which the minimum distance from the origin along any path constructed from previously observed edges, MinObservedDist[origin](v), is equal to the minimum distance from the origin along any path, MinDist[origin](v). These vertices are "finalized" in the sense that we have successfully computed the actual minimum distance to them from the origin vertex. We can refer to this property as the finality of the metadata for finalized vertices.

Property 2: MinObservedDist for vertices on the frontier of Finalized ー that is, vertices not in Finalized themselves but that are the destination vertex for a crossing edge originating from a vertex inside Finalized ーis set to the minimum distance along any path from the origin vertex to them that goes through a crossing edge that ends in them. We can refer to this as the up-to-dateness property of the vertices on the frontier. Very clumsy wording in this paragraph.

Given this situation, what is the next vertex w outside of Finalized that we can move into Finalized? That is, which one do we have enough information to compute the actual minimum distance from the origin vertex for?

It is the vertex w on the frontier Finalized with the smallest value for MinObservedDist[origin]( w). (Any vertex not on the frontier of finalized has a MinObservedDist[origin] of INF.) To see why, consider any path to w from the origin vertex.

Since w is not inside Finalized, at some point this path must include a crossing edge ce from inside Finalized to the frontier of Finalized. We'll refer to the endpoints of this crossing edge as ce.src and ce.dest, ce.src being inside Finalized and ce.dest being on the frontier of Finalized. This path can be thus be broken down in the following segments: the segment from the origin vertex to ce.src, the crossing edge ce, and the segment from ce.dest to w.

By the up-to-dateness property of the vertices on the frontier, the length of the first two segments is >= MinObservedDist[origin](ce.src) + ce.length, which in turn is >= MinObservedDist[origin](ce.dest). Since the edges in the input graph are stipulated to be non-negative, the third segment of the path contributes 0 or greater to the total length of the path; therefore, the length of the whole path is also >= MinObservedDist[origin](ce.dest).

Due to the finality of the metadata for vertices inside Finalized, MinObservedDist[origin](ce.src) is MinDist[origin](ce.src) and the length of the first two segments is >= MinObservedDist[origin](ce.src) + ce.length, which in turn is >= MinObservedDist[origin](ce.dest) ー by the update-to-dateness property of the vertices on the frontier, MinObservedDist[origin](ce.dest) is truly the shortest distance along any path from the origin vertex to ce.dest through a crossing edge that ends in ce.dest.

Since w is the vertex on the frontier of Finalized with the smallest value for MinObservedDist[origin], we know that MinObservedDist[origin](ce.dest) >= MinObservedDist[origin](w). Hence, MinObservedDist[origin](w) is the lower bound for any path from the origin vertex to w, meaning MinObservedDist[origin](w) = MinDist[origin](w) and we can add it to Finalized.

Note that adding a new vertex to Finalized adds new vertices to its frontier, which breaks the up-to-dateness of the metadata for non-finalized vertices on the frontier. This property needs to be re-established immediately. So MinObservedDist[origin] needs to be re-computed for the newly finalized vertex's non-finalized neighbors, taking the new crossing edges into account.

In summary, we have shown that, given two properties, we are able to add a new vertex to the set of finalized vertices. Doing so breaks one of the two properties, but we were able to come up with a mechanism to re-establish it, putting us in position to add yet another vertex to the set of finalized vertices. So as long as we are able to establish the two properties once, we should be able to continue adding vertices to Finalized until we have added all vertices reachable from the origin vertex.

[darwinrlo]

KEEPING THE METADATA FOR NON-FINALIZED VERTICES ON THE FRONTIER UP-TO-DATE

The metadata for non-finalized vertices is dependent upon what currently constitutes the frontier of the finalized nodes. Recall that MinObservedDist[origin] for a non-finalized vertex v is the minimum distance along any path from the origin vertex to v through a crossing edge that ends in v. So when a new vertex is finalized, the vertex's non-finalized neighbors are now incident on crossing edges, meaning their metadata need to be updated.

[darwinrlo]

ESTABLISHING THE TWO PROPERTIES

• Set MinObservedDist[origin](origin) to 0. This is MinDist[origin](origin) because there is no distance between the origin vertex and itself.
• Let Finalized be an empty set. Add the origin vertex to it and update MinObservedDist[origin] for vertices to which there is an edge from the origin vertex. These vertices make up the frontier of Finalized, which for now consists of just the origin vertex, and for each such vertex v, MinObservedDist[origin](v) is simply ShortestEdge(origin, v).length.

At this point, even though it's just the origin vertex, Finalized consists of only finalized vertices. And its frontier -- the vertices to which there is an outgoing edge from the origin vertex -- have up-to-date values for MinObservedDist[origin]. The two properties we need to start adding vertices hold, and we are well-poised to add the remainder of the graph's vertices, at least those that are reachable from the origin vertex.