1.4.4 Shortest Path

INPUT OUTPUT
Input Description:
An edge-weighted graph G, with start vertex s and
end vertex t.
Problem:
Find the shortest path from s to t in G.
Excerpt from
The Algorithm Design Manual:
The problem of finding shortest paths in a graph
has a surprising variety of applications:
- The most obvious applications arise in transportation or communications,
such as finding the best route to drive between Chicago and Phoenix or figuring how to
direct packets to a destination across a network.
- Consider the problem of image segmentation, that is, separating two characters in a scanned, bit-mapped
image of printed text. We need to find the separating line between two points that cuts through the fewest number
of black pixels. This grid of pixels can be modeled as a graph, with any edge across a black pixel given a high
cost. The shortest path from top to bottom defines the best separation between
left and right.
- A major problem in speech recognition is distinguishing between words
that sound alike (homophones), such as to, two, and too.
We can construct a graph whose vertices correspond to possible
words, with an edge between possible neighboring words.
If the weight of each edge measures the likelihood of transition, the shortest
path across the graph defines the best interpretation of a sentence.
- Suppose we want to draw an informative picture of a graph.
The center of the page should coorespond to the ``center'' of the graph,
whatever that means.
A good definition of the center is the vertex that minimizes the maximum
distance to any other vertex in the graph.
Finding this center point requires knowing the distance (i.e. shortest
path) between all pairs of vertices.
The best book available for this problem is
Network Flows : Theory, Algorithms, and Applications
by
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.
Implementations
Goldberg's Network Optimization Codes (C) (rating 9)
LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
Discrete Optimization Methods (Pascal) (rating 5)
Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)
The Stanford GraphBase (C) (rating 3)
Combinatorica (Mathematica) (rating 3)
Related Problems
Connected Components
Graph Isomorphism
Matrix Multiplication
Motion Planning
Network Flow
Priority Queues
Steiner Tree
Transitive Closure and Reduction
Previous Problem
Next Problem
View the graph for this
file
Bulletin Board
About ``The Algorithm Design Manual''.
Send us Mail
The Stony Brook Algorithm Repository -- go to front page
This page last modified on Wed Mar 07, 2001
.