Java Reference
In-Depth Information
FIGURE 28-20
The graph in Figure 28-18a after finding the cheapest path from
vertex
A
to vertex
H
5
2
A
0
D
5A
G7D
4
2
1
6
B2A
E3B
H8G
1
3
3
1
3
F6E
C0
I0
4
1
28.24
The algorithm.
The pseudocode for the algorithm we just described follows. Objects in the priority
queue are instances of a private class
EntryPQ
. Following the traversal, the algorithm pushes the
vertices that occur along the cheapest path from
originVertex
to
endVertex
into a given, initially
empty stack
path
.
Algorithm
getCheapestPath(originVertex, endVertex, path)
done =
false
priorityQueue =
a new priority queue
priorityQueue.add(
new
EntryPQ(originVertex, 0,
null
))
while
(!done && !priorityQueue.isEmpty())
{
frontEntry = priorityQueue.remove()
frontVertex =
vertex in
frontEntry
if
(frontVertex is
not visited
)
{
Mark
frontVertex
as visited
Set the cost of the path to
frontVertex
to the cost recorded in
frontEntry
Set the predecessor of
frontVertex
to the predecessor recorded in
frontEntry
if
(frontVertex
equals
endVertex)
done =
true
else
{
while
(frontVertex
has a neighbor
)
{
nextNeighbor =
next neighbor of
frontVertex
weightOfEdgeToNeighbor =
weight of edge to
nextNeighbor
if
(nextNeighbor
is not visited
)
{
nextCost = weightOfEdgeToNeighbor +
cost of path to
frontVertex
priorityQueue.add(
new
EntryPQ(nextNeighbor, nextCost,
frontVertex))
}
}
}
}
}
//
traversal ends; construct cheapest path
