05-03-2013, 02:04 PM
Shortest Paths
Shortest Paths.pdf (Size: 1.69 MB / Downloads: 402)
Early history of shortest paths algorithms
Shimbel (1955). Information networks.
Ford (1956). RAND, economics of transportation.
Leyzorek, Gray, Johnson, Ladew, Meaker, Petry, Seitz (1957).
Combat Development Dept. of the Army Electronic Proving Ground.
Dantzig (1958). Simplex method for linear programming.
Bellman (1958). Dynamic programming.
Moore (1959). Routing long-distance telephone calls for Bell Labs.
Dijkstra (1959). Simpler and faster version of Ford's algorithm
Applications
Shortest-paths is a broadly useful problem-solving model
• Maps
• Robot navigation.
• Texture mapping.
• Typesetting in TeX.
• Urban traffic planning.
• Optimal pipelining of VLSI chip.
• Subroutine in advanced algorithms.
• Telemarketer operator scheduling.
• Routing of telecommunications messages.
• Approximating piecewise linear functions.
• Network routing protocols (OSPF, BGP, RIP).
• Exploiting arbitrage opportunities in currency exchange.
• Optimal truck routing through given traffic congestion pattern.
Single-source shortest-paths: basic plan
Goal: Find distance (and shortest path) from s to every other vertex.
Design pattern:
• ShortestPaths class (WeightedDigraph client)
• instance variables: vertex-indexed arrays dist[] and pred[]
• client query methods return distance and path iterator
Shortest paths summary
Dijkstra’s algorithm
• easy and optimal for dense digraphs
• PQ/ST data type gives near optimal for sparse graphs
Priority-first search
• generalization of Dijkstra’s algorithm
• encompasses DFS, BFS, and Prim
• enables easy solution to many graph-processing problems
Negative weights
• arise in applications
• make problem intractable in presence of negative cycles (!)
• easy solution using old algorithms otherwise