Java Reference
In-Depth Information
Let us illustrate Dijkstra's algorithm using the graph in Figure 29.11a. Suppose the source
vertex is
1
. Therefore,
cost[1] = 0
and the costs for all other vertices are initially
, as
shown in Figure 29.11b. We use the
parent[i]
to denote the parent of
i
in the path. For
convenience, set the parent of the source node to
-1
.
∞
1
10
3
cost
5
9
5
8
0
2
0123456
8
8
6
4
parent
1
-1
2
7
5
0123456
0
4
5
(a)
(b)
F
IGURE
29.11
The algorithm will find all shortest paths from source vertex
1
.
Initially set
T
is empty. The algorithm selects the vertex with the smallest cost. In this case,
the vertex is
1
. The algorithm adds
1
to
T
, as shown in Figure 29.12a. Afterwrads, it adjusts
the cost for each vertex adjacent to
1
. The cost for vertices 2, 0, 6, and 3 and their parents are
now updated, as shown, as shown in Figure 29.12b.
T
1
10
3
cost
5
9
5
8
8
0
50
9
2
0123456
8
8
6
4
parent
1
1
-1
1
1
1
5
2
7
0123456
0
4
5
(a)
(b)
F
IGURE
29.12
Now vertex
1
is in set
T
.
Vertices
2
,
0
,
6
, and
3
are adjacent to the source vertex, and vertex
2
is the one in
V-T
with the smallest cost, so add
2
to
T
, as shown in Figure 29.13 and update the cost and
parent for vertices in
V-T
and adjacent to
2
.
cost[0]
is now updated to
6
and its parent is
set to
2
. The arrow line from
1
to
2
indicates that
1
is the parent of
2
after
2
is added into
T
.
Search WWH ::
Custom Search