Java Reference
In-Depth Information
figure 14.25
Stages of Dijkstra's
algorithm. The
conventions are the
same as those in
Figure 14.21.
0
0
2
2
2
V
0
V
1
V
0
V
1
4
4
1
3
1
3
10
10
1
2
2
2
2
V
2
V
3
V
4
V
2
V
3
V
4
5
8
4
6
5
8
4
6
1
1
1
2
V
5
V
6
V
5
V
6
0
0
2
2
2
2
V
0
V
1
V
0
V
1
4
4
1
3
1
3
10
10
1
1
3
3
3
3
2
2
2
2
V
2
V
3
V
4
V
2
V
3
V
4
5
8
4
6
5
8
4
6
5
5
9
9
1
1
3
4
V
5
V
6
V
5
V
6
0
0
2
2
2
2
V
0
V
1
V
0
V
1
4
4
1
3
1
3
1
10
10
3
3
1
3
3
2
2
2
2
V
2
V
3
V
4
V
2
V
3
V
4
5
8
4
6
5
8
4
6
5
5
9
8
1
1
5
6
V
5
V
6
V
5
V
6
0
0
2
2
2
2
V
0
V
1
V
0
V
1
4
4
1
3
1
3
10
10
1
1
3
3
3
3
The priority queue is
an appropriate data
structure. The easi-
est method is to
add a new entry,
consisting of a ver-
tex and a distance,
to the priority queue
every time a vertex
has its distance
lowered. We can
find the new vertex
to move to by
repeatedly remov-
ing the minimum
distance vertex
from the priority
queue until an
unvisited vertex
emerges.
2
2
2
2
V
2
V
3
V
4
V
2
V
3
V
4
5
8
4
6
5
8
4
6
5
5
6
6
1
1
7
8
V
5
V
6
V
5
V
6
priority queue and use the distance (obtained by consulting the graph table) as
the ordering function. When we alter any
,
we must update the priority
queue by reestablishing the ordering property. This action amounts to a
decreaseKey
operation. To take it we need to be able to find the location of
w
in
the priority queue. Many implementations of the priority queue do not support
decreaseKey
. One that does is the
pairing heap
;
we discuss use of the pairing
heap for this application in Chapter 23.
D
w
Search WWH ::
Custom Search