Java Reference
In-Depth Information
If we move the eyeball to the unseen vertex with minimum , the algorithm correctly
produces the shortest paths if there are no negative edge costs.
D i
Theorem 14.1
Proof
Call each eyeball visit a “stage.” We prove by induction that, after any stage, the val-
ues of for vertices visited by the eyeball form the shortest path and that the val-
ues of for the other vertices form the shortest path using only vertices visited by
the eyeball as intermediates. Because the first vertex visited is the starting vertex,
this statement is correct through the first stage. Assume that it is correct for the first
k stages. Let v be the vertex chosen by the eyeball in stage . Suppose, for the
purpose of showing a contradiction, that there is a path from S to v of length less
than .
This path must go through an intermediate vertex that has not yet been visited by
the eyeball. Call the first intermediate vertex on the path not visited by the eyeball u .
This situation is shown in Figure 14.24. The path to u uses only vertices visited by the
eyeball as intermediates, so by induction, represents the optimal distance to u .
Moreover, , because u is on the supposed shorter path to v . This inequality is
a contradiction because then we would have moved the eyeball to u instead of v . The
proof is completed by showing that all the
D i
D i
k
+
1
D v
D u
D u D v
<
D i
values remain correct for nonvisited
nodes, which is clear by the update rule.
figure 14.24
If D v is minimal
among all unseen
vertices and if all edge
costs are nonnegative,
D v represents the
shortest path.
D v
v
0
S
d - 0
D u
u
Figure 14.25 shows the stages of Dijkstra's algorithm. The remaining
issue is the selection of an appropriate data structure. For dense graphs, we
can scan down the graph table looking for the appropriate vertex. As with the
unweighted shortest-path algorithm, this scan will take time, which
is optimal for a dense graph. For a sparse graph, we want to do better.
Certainly, a queue does not work. The fact that we need to find the vertex
v with minimum suggests that a priority queue is the method of choice.
There are two ways to use the priority queue. One is to store each vertex in the
OV 2
(
)
D v
Search WWH ::




Custom Search