next up previous index CD Book Algorithms
Next: Lecture 19 - satisfiability Up: No Title Previous: Lecture 17 - minimum

Lecture 18 - shortest path algorthms

Listen To Part 20-7

25.1-1 Give two more shortest path trees for the following graph:


Run through Dijkstra's algorithm, and see where there are ties which can be arbitrarily selected.  

There are two choices for how to get to the third vertex x, both of which cost 5.

There are two choices for how to get to vertex v, both of which cost 9.

Listen To Part 19-1

Lessons from the Backtracking contest

Listen To Part 19-3

Winning Optimizations

Listen To Part 19-10

Shortest Paths

Finding the shortest path between two nodes in a graph arises in many different applications:  

Listen To Part 20-1

Shortest Paths and Sentence Disambiguation

In our work on reconstructing text typed on an (overloaded) telephone keypad, we had to select which of many possible interpretations was most likely.   

We constructed a graph where the vertices were the possible words/positions in the sentence, with an edge between possible neighboring words.

Listen To Part 20-2

The weight of each edge is a function of the probability that these two words will be next to each other in a sentence. `hive me' would be less than `give me', for example.

The final system worked extremely well - identifying over 99% of characters correctly based on grammatical and statistical constraints.

Dynamic programming (the Viterbi algorithm) can be used on the sentences to obtain the same results, by finding the shortest paths in the underlying DAG.  

Listen To Part 20-3

Finding Shortest Paths

In an unweighted graph, the cost of a path is just the number of edges on the shortest path, which can be found in O(n+m) time via breadth-first search.  

In a weighted graph, the weight of a path between two vertices is the sum of the weights of the edges on a path.

BFS will not work on weighted graphs because sometimes visiting more edges can lead to shorter distance, ie. 1+1+1+1+1+1+1 < 10.

Note that there can be an exponential number of shortest paths between two nodes - so we cannot report all shortest paths efficiently.

Note that negative cost cycles render the problem of finding the shortest path meaningless, since you can always loop around the negative cost cycle more to reduce the cost of the path.

Thus in our discussions, we will assume that all edge weights are positive. Other algorithms deal correctly with negative cost edges.

Minimum spanning trees are uneffected by negative cost edges.

Listen To Part 20-4

Dijkstra's Algorithm

We can use Dijkstra's algorithm to find the shortest path between any two vertices and t in G.  

The principle behind Dijkstra's algorithm is that if tex2html_wrap_inline15602 is the shortest path from to t, then tex2html_wrap_inline15604 had better be the shortest path from to x.

This suggests a dynamic programming-like strategy, where we store the distance from to all nearby nodes, and use them to find the shortest path to more distant nodes.

The shortest path from to , d(,)=0. If all edge weights are positive, the smallest edge incident to , say (,x), defines d(,x).

We can use an array to store the length of the shortest path to each node. Initialize each to tex2html_wrap_inline15612 to start.

Soon as we establish the shortest path from to a new node x, we go through each of its incident edges to see if there is a better way from to other nodes thru x.

Listen To Part 20-5


for i=1 to n, tex2html_wrap_inline15618

for each edge (,v), dist[v]=d(,v)


while ( tex2html_wrap_inline15624 )

select v such that tex2html_wrap_inline15626

for each (v,x), tex2html_wrap_inline15630



Complexity tex2html_wrap_inline15634 tex2html_wrap_inline15636 if we use adjacency lists and a Boolean array to mark what is known.

This is essentially the same as Prim's algorithm.

An tex2html_wrap_inline15638 implementation of Dijkstra's algorithm would be faster for sparse graphs, and comes from using a heap of the vertices (ordered by distance), and updating the distance to each vertex (if necessary) in tex2html_wrap_inline15640 time for each edge out from freshly known vertices.

Even better, tex2html_wrap_inline15642 follows from using Fibonacci heaps, since they permit one to do a decrease-key operation in O(1) amortized time.

Listen To Part 20-8

All-Pairs Shortest Path

Notice that finding the shortest path between a pair of vertices (,t) in worst case requires first finding the shortest path from to all other vertices in the graph.  

Many applications, such as finding the center or diameter of a graph, require finding the shortest path between all pairs of vertices.

We can run Dijkstra's algorithm n times (once from each possible start vertex) to solve all-pairs shortest path problem in tex2html_wrap_inline15648 . Can we do better?

Improving the complexity is an open question but there is a super-slick dynamic programming algorithm which also runs in tex2html_wrap_inline15650 .

Listen To Part 20-9

Dynamic Programming and Shortest Paths

The four-step approach to dynamic programming is:

  1. Characterize the structure of an optimal solution.
  2. Recursively define the value of an optimal solution.
  3. Compute this recurrence in a bottom-up fashion.
  4. Extract the optimal solution from computed information.

From the adjacency matrix, we can construct the following matrix:

tex2html_wrap_inline15652 , if tex2html_wrap_inline15654 and tex2html_wrap_inline15656 is not in E

D[i,j] = w(i,j), if tex2html_wrap_inline15660

D[i,j] = 0, if i=j

This tells us the shortest path going through no intermediate nodes.

There are several ways to characterize the shortest path between two nodes in a graph. Note that the shortest path from i to j, tex2html_wrap_inline15666 , using at most M edges consists of the shortest path from i to k using at most M-1 edges + W(k, j) for some k.

Listen To Part 20-10

This suggests that we can compute all-pair shortest path with an induction based on the number of edges in the optimal path.

Let tex2html_wrap_inline15670 be the length of the shortest path from i to j using at most m edges.

What is tex2html_wrap_inline15672 ?


What if we know tex2html_wrap_inline15674 for all i,j?


since w[k, k]=0

This gives us a recurrence, which we can evaluate in a bottom up fashion:

for i=1 to n

for j=1 to n


for k=1 to n

tex2html_wrap_inline15686 =Min( tex2html_wrap_inline15688 , tex2html_wrap_inline15690 )

This is an tex2html_wrap_inline15692 algorithm just like matrix multiplication, but it only goes from m to m+1 edges.

Listen To Part 20-11

Since the shortest path between any two nodes must use at most n edges (unless we have negative cost cycles), we must repeat that procedure n times (m=1 to n) for an tex2html_wrap_inline15696 algorithm.

We can improve this to tex2html_wrap_inline15698 with the observation that any path using at most 2m edges is the function of paths using at most m edges each. This is just like computing tex2html_wrap_inline15700 . So a logarithmic number of multiplications suffice for exponentiation.

Although this is slick, observe that even tex2html_wrap_inline15702 is slower than running Dijkstra's algorithm starting from each vertex!

Listen To Part 20-12

The Floyd-Warshall Algorithm


An alternate recurrence yields a more efficient dynamic programming formulation. Number the vertices from 1 to n.

Let tex2html_wrap_inline15704 be the shortest path from i to j using only vertices from 1, 2,..., k as possible intermediate vertices.

What is tex2html_wrap_inline15708 ? With no intermediate vertices, any path consists of at most one edge, so tex2html_wrap_inline15710 .

In general, adding a new vertex k+1 helps iff a path goes through it, so


Although this looks similar to the previous recurrence, it isn't. The following algorithm implements it:


for k=1 to n

for i=1 to n

for j=1 to n


This obviously runs in tex2html_wrap_inline15722 time, which asymptotically is no better than a calls to Dijkstra's algorithm. However, the loops are so tight and it is so short and simple that it runs better in practice by a constant factor.

next up previous index CD Book Algorithms
Next: Lecture 19 - satisfiability Up: No Title Previous: Lecture 17 - minimum

Mon Jun 2 09:21:39 EDT 1997