Java Reference
In-Depth Information
B
5
10
D
20
A
11
2
3
15
C
E
Figure11.16
Example graph for shortest-path definitions.
orithm (in the worst case) for finding the shortest path to a single vertex than to find
shortest paths to all vertices. The algorithm described here will only compute the
distance to every such vertex, rather than recording the actual path. Recording the
path requires modifications to the algorithm that are left as an exercise.
Computer networks provide an application for the single-source shortest-paths
problem. The goal is to find the cheapest way for one computer to broadcast a
message to all other computers on the network. The network can be modeled by a
graph with edge weights indicating time or cost to send a message to a neighboring
computer.
For unweighted graphs (or whenever all edges have the same cost), the single-
source shortest paths can be found using a simple breadth-first search.
When
weights are added, BFS will not give the correct answer.
One approach to solving this problem when the edges have differing weights
might be to process the vertices in a fixed order. Label the vertices v
0
to v
n1
, with
S = v
0
. When processing Vertex v
1
, we take the edge connecting v
0
and v
1
. When
processing v
2
, we consider the shortest distance from v
0
to v
2
and compare that to
the shortest distance from v
0
to v
1
to v
2
. When processing Vertex v
i
, we consider
the shortest path for Vertices v
0
through v
i1
that have already been processed.
Unfortunately, the true shortest path to v
i
might go through Vertex v
j
for j > i.
Such a path will not be considered by this algorithm. However, the problem would
not occur if we process the vertices in order of distance from S. Assume that we
have processed in order of distance from S to the first i1 vertices that are closest
to S; call this set of vertices S. We are now about to process the ith closest vertex;
call it X. A shortest path from S to X must have its next-to-last vertex in S. Thus,
d(S; X) = min
U
2
S
(d(S; U) + w(U; X)):
In other words, the shortest path from S to X is the minimum over all paths that go
from S to U, then have an edge from U to X, where U is some vertex in S.
This solution is usually referred to as Dijkstra's algorithm. It works by main-
taining a distance estimate D(X) for all vertices X in V. The elements of D are ini-
