Java Reference
In-Depth Information
shortest path from
s
to all vertices. So
Dijkstra's algorithm
is known as a
single-source
shortest
path algorithm. The algorithm uses
cost[v]
to store the cost of a
shortest path
from vertex
v
to
the source vertex
s
.
cost[s]
is
0
. Initially assign infinity to
cost[v]
for all other vertices. The
algorithm repeatedly finds a vertex
u
in
V - T
with the smallest
cost[u]
and moves
u
to
T
.
The algorithm is described in Listing 29.7.
single-source shortest path
L
ISTING
29.7
Dijkstra's Single-Source Shortest-Path
Algorithm
Input: a graph G = (V, E) with non-negative weights
Output: a shortest path tree with the source vertex s as the root
1 ShortestPathTree getShortestPath(s) {
2 Let T be a set that contains the vertices whose
3 paths to s are known; Initially T is empty;
4 Set cost[s] =
0
; and cost[v] = infinity for all other vertices in V;
5
6
while
(size of T < n) {
7 Find u not in T with the smallest cost[u];
8 Add u to T;
9 for (each v not in T and (u, v) in E)
10 if (cost[v] > cost[u] + w(u, v)) {
11 cost[v] = cost[u] + w(u, v); parent[v] = u;
12 }
13 }
14 }
find next vertex
add a vertex to T
adjust cost[v]
This algorithm is very similar to Prim's for finding a minimum spanning tree. Both algorithms
divide the vertices into two sets:
T
and
V - T
. In the case of Prim's algorithm, set
T
contains
the vertices that are already added to the tree. In the case of Dijkstra's, set
T
contains the
vertices whose shortest paths to the source have been found. Both algorithms repeatedly find
a vertex from
V- T
and add it to
T
. In the case of Prim's algorithm, the vertex is adjacent
to some vertex in the set with the minimum weight on the edge. In Dijkstra's algorithm, the
vertex is adjacent to some vertex in the set with the minimum total cost to the source.
The algorithm starts by setting
cost[s]
to
0
(line 4), sets
cost[v]
to infinity for all other
vertices. It then continuously adds a vertex (say
u
) from
V - T
into
T
with smallest
cost[u]
(lines 7-8), as shown in Figure 29.10a. After adding
u
to
T
, the algorithm updates
cost[v]
and
parent[v]
for each
v
not in
T
if
(u, v)
is in
T
and
cost[v] > cost[u] + w(u, v)
(lines 10-11).
T contains
vertices whose
shortest path to s
are known
V - T contains vertices whose shortest
path to s are not known yet.
T contains
vertices whose
shortest path to s
are known
V - T contains vertices whose shortest
path to s are not known yet.
V
-
T
V
-
T
v
1
v
1
u
T
T
v
2
v
2
s
s
u
v
3
v
3
(a) Before moving
u
to
T
(b) After moving
u
to
T
F
IGURE
29.10
(a) Find a vertex
u
in
V - T
with the smallest
cost[u]
. (b) Update
cost[v]
for v in
V - T
and
v
is
adjacent to
u
.
Search WWH ::
Custom Search