CSc 352: Shortest Path Computations

Background

There are many different algorithms for computing shortest paths in graphs. The goal of a single-source shortest paths problem is to determine the shortest path from a given vertex in a graph to every other vertex. There are also all-pairs shortest paths algorithms that compute the shortest distance between each pair of vertices in the graph. We'll use the single-source version for simplicity. The one described here is known as Dijkstra's single-source shortest path algorithm: it assumes that the distances between cities (i.e., the weights on the edges of the graph) are all non-negative.

Suppose we have a graph G and a source vertex s: we want to determine the shortest distance from the source s to the other vertices. (Strictly speaking, we want to know only the shortest distance between two given vertices. It turns out that, in order to do this, we need to compute the shortest distances to ``intermediate'' vertices. So the bottom line is that we compute shortest distances from the source vertex to all other vertices.)

The basic idea of the algorithm is to maintain a set of vertices for which we already know the shortest distance from the source s; we'll mark these vertices (``marking'' a vertex means setting a bit in the record for that vertex, analogous to the way vertices were flagged as ``visited'' in the reachability problem). As the algorithm executes, therefore, we have two classes of vertices:

The essential idea in the algorithm is to iterate over the vertices in the graph: in each iteration we are able to take an unmarked vertex and compute the exact shortest distance to it. The algorithm terminates when all vertices are marked (assuming that the graph is connected).

Data Structures

The data structure for this is in many ways similar to that for the Graph Reachability problem (Assignment 6), with the following differences:

  1. Each edge e now has an additional field dist, an integer, which gives the value of ths distance between the two endpoints of that edge.

  2. Each vertex v now has an additional field minDist, an integer, that gives the shortest distance from the source to that vertex.

Initialization

Initially, all we can say about the shortest distances is that the shortest distance from the source vertex to itself is 0. For all the other vertices, we set the minDist field to infinity (actually, to INT_MAX : see Appendix B11, p. 257 of the C text by Kernighan and Ritchie). Thus, this phase looks like:
for each vertex v {
  v.minDist = INT_MAX;
  unmark v;
}
src.minDist = 0;

Iteration

The main idea in the iteration is to find, at each iteration, a vertex u to which we already know the exact shortest distance from the source (as mentioned in the Initialization phase above, initially the only such vertex is the source itself), then use this to improve our estimate of the minDist field of all of the neighbors of u.

Suppose that a vertex v is a neighbor of u, where e is the edge between u and v. Now v.minDist is our current approximation to the shortest distance from the source to v. Suppose that we find that

u.minDist + e.dist < v.minDist
then (since by hypothesis we already know the shortest distance to u) this means that we've managed to find a shorter path than before from the source vertex to v, through the vertex u and then using the edge e. This means that we now have a better approximation to the shortest distance from the source to v. We accordingly set v.minDist to the new value.

As you can see, whenever a vertex v has its minDist field updated, the new value is obtained by adding an e.dist value to the minDist field of one of its neighbors. Under the assumption that all edges have nonnegative weights, i.e., e.dist >= 0 for all edges e, this means that if w is an unmarked vertex with the smallest minDist value of all the unmarked vertices, then its value can't get any smaller. So we can mark the vertex w, i.e., conclude that we've found the shortest distance from the source to w. (Actually, during each round of iteration we do this step first, then update the minDist fields of w's neighbors: this is discussed below.)

The Overall Algorithm

The algorithm consists of the following steps:

  1. Initialize, as discussed above.

  2. repeat until no new vertex can be marked:

    1. Let u be an unmarked vertex that has the smallest minDist value among all the unmarked vertices.

    2. Mark the vertex u.

    3. For each vertex v that is a neighbor of u:

      1. let u and v be joined by the edge e, where e.dist gives the distance between u and v.

      2. We improve our estimates of the field v.minDist as follows:
        n = u.minDist + e.dist;
        if (n < v.minDist) then v.minDist = n.

  3. If there are any unmarked vertices left, the graph is not connected.

In your implementation, you should make sure that the initialization step is carried out for each query, i.e., each pair of cities for which we want to compute the shortest distance. Choose one of the two cities as the source (it doesn't matter which one), run the algorithm, and then print out the minDist field for the other one.