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).
for each vertex v { v.minDist = INT_MAX; unmark v; } src.minDist = 0;
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.minDistthen (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.)
n = u.minDist + e.dist;
if (n < v.minDist) then v.minDist = n.
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.