Shortest-Path Algorithms

• The input is a weighted graph: associated with each edge (vi, vj) is a cost ci, j to traverse the edge. The cost of a path v1v2 … vN is Σi=1N−1 ci,i+1. This is referred to as the weighted path length. The unweighted path length is merely the number of edges on the path, namely, N − 1.
• Generally, when it is not specified whether we are referring to a weighted or an unweighted path, the path is weighted if the graph is.
• egative-cost cycle; when one is present in the graph, the shortest paths are not defined.
• Negative-cost edges are not necessarily bad, as the cycles are, but their presence seems to make the problem harder.
• This figure shows an unweighted graph, G. Using some vertex, s, which is an input parameter, we would like to find the shortest path from s to all other vertices. We are only interested in the number of edges contained on the path, so there are no weights on the edges. This is clearly a special case of the weighted shortest-path problem, since we could assign all edges a weight of 1.

  
• Suppose we choose s to be v3. Immediately, we can tell that the shortest path from s to v3 is then a path of length 0.

  
• Now we can start looking for all vertices that are a distance 1 away from s. These can be found by looking at the vertices that are adjacent to s. If we do this, we see that v1 and v6 are one edge from s.

  
• We can now find vertices whose shortest path from s is exactly 2, by finding all the vertices adjacent to v1 and v6 (the vertices at distance 1), whose shortest paths are not already known. This search tells us that the shortest path to v2 and v4 is 2.

  
• Finally we can find, by examining vertices adjacent to the recently evaluated v2 and v4, that v5 and v7 have a shortest path of three edges. All vertices have now been calculated,

  
• breadth-first search. It operates by processing vertices in layers: The vertices closest to the start are evaluated first, and the most distant vertices are evaluated last. This is much the same as a level-order traversal for trees.
• For each vertex, we will keep track of three pieces of information. First, we will keep its distance from s in the entry dv. Initially all vertices are unreachable except for s, whose path length is 0. The entry in pv is the bookkeeping variable, which will allow us to print the actual paths. The entry known is set to true after a vertex is processed. Initially, all entries are not known, including the start vertex. When a vertex is marked known, we have a guarantee that no cheaper path will ever be found, and so processing for that vertex is essentially complete.
• The running time of the algorithm is O(|V|2), because of the doubly nested for loops. An obvious inefficiency is that the outside loop continues until NUM_VERTICES − 1, even if all the vertices become known much earlier.
• We can remove the inefficiency in much the same way as was done for topological sort. At any point in time, there are only two types of unknown vertices that have dv ≠ ∞. Some have dv = currDist and the rest have dv = currDist + 1. Because of this extra structure, it is very wasteful to search through the entire table to find a proper vertex.
• In the pseudocode, we have assumed that the start vertex, s, is passed as a parameter. Also, it is possible that the queue might empty prematurely, if some vertices are unreachable from the start node. In this case, a distance of INFINITY will be reported for these nodes, which is perfectly reasonable. Finally, the known field is not used; once a vertex is processed it can never enter the queue again, so the fact that it need not be reprocessed is implicitly marked. Thus, the known field can be discarded.

  
• If the graph is weighted, We keep all of the same information as before. Thus, each vertex is marked as either known or unknown. A tentative distance dv is kept for each vertex, as before. This distance turns out to be the shortest path length from s to v using only known vertices as intermediates. As before, we record pv, which is the last vertex to cause a change to dv.
• The general method to solve the single-source shortest-path problem is known as Dijkstra’s algorithm.
• Dijkstra’s algorithm is a prime example of a greedy algorithm.
• Greedy algorithms generally solve a problem in stages by doing what appears to be the best thing at each stage.
• Dijkstra’s algorithm proceeds in stages, just like the unweighted shortest-path algorithm. At each stage, Dijkstra’s algorithm selects a vertex v, which has the smallest dv among all the unknown vertices, and declares that the shortest path from s to v is known. The remainder of a stage consists of updating the values of dw.
• In the unweighted case, we set dw = dv + 1 if dw = ∞. Thus, we essentially lowered the value of dw if vertex v offered a shorter path. If we apply the same logic to the weighted case, then we should set dw = dv + cv,w if this new value for dw would be an improvement. Put simply, the algorithm decides whether or not it is a good idea to use v on the path to w. The original cost, dw, is the cost without using v; the cost calculated above is the cheapest path using v (and only known vertices)
• To print out the actual path from a start vertex to some vertex v, we can write a recursive routine to follow the trail left in the p variables.
• Dijkstra: selection of the vertex v is a deleteMin operation, since once the unknown minimum vertex is found, it is no longer unknown and must be removed from future consideration.
• If the graph has negative edge costs, then Dijkstra’s algorithm does not work. The problem is that once a vertex u is declared known, it is possible that from some other, unknown vertex v there is a path back to u that is very negative.
• If the graph is known to be acyclic, we can improve Dijkstra’s algorithm by changing the order in which vertices are declared known, otherwise known as the vertex selection rule. The new rule is to select vertices in topological order. The algorithm can be done in one pass, since the selections and updates can take place as the topological sort is being performed.