Graphs and paths - Data Structures and Problem Solving Using Java - page 550

Rather than use a fancy priority queue, we use a method that works with a
simple priority queue, such as the binary heap, to be discussed in Chapter 21. Our
method involves inserting an object consisting of w and D w in the priority queue
whenever we lower D w . To select a new vertex v for visitation, we repeatedly
remove the minimum item (based on distance) from the priority queue until an
unvisited vertex emerges. Because the size of the priority queue could be as large
as and there are at most priority queue insertions and deletions, the run-
ning time is . Because implies , we
have the same algorithm that we would have if we used the first
method (in which the priority queue size is at most

E E

OE E ( log ) EV 2 ≤ log E ≤ 2 log V

OE V ( log )

V ).

14.3.2 java implementation

The object placed on the priority queue is shown in Figure 14.26. It consists
of w and D w and a comparison function defined on the basis of D w .
Figure 14.27 shows the routine dijkstra that calculates the shortest paths.
Line 6 declares the priority queue pq . We declare vrec at line 18 to store
the result of each deleteMin . As with the unweighted shortest-path algorithm,
we begin by setting all distances to infinity, setting D S = 0, and placing the
starting vertex in our data structure.

Again, the implemen-
tation follows the
description fairly
closely.

1 // Represents an entry in the priority queue for Dijkstra's algorithm.
2 class Path implements Comparable<Path>
3 {
4 public Vertex dest; // w
5 public double cost; // d(w)
6
7 public Path( Vertex d, double c )
8 {
9 dest = d;
10 cost = c;
11 }
12
13 public int compareTo( Path rhs )
14 {
15 double otherCost = rhs.cost;
16
17 return cost < otherCost ? -1 : cost > otherCost ? 1 : 0;
18 }
19 }

figure 14.26
Basic item stored in the priority queue