Merging priority queues - Data Structures and Problem Solving Using Java - page 887

1 /**
2 * Single-source weighted shortest-path algorithm using pairing heaps.
3 */
4 public void dijkstra( String startName )
5 {
6 PairingHeap<Path> pq = new PairingHeap<Path>( );
7
8 Vertex start = vertexMap.get( startName );
9 if( start == null )
10 throw new NoSuchElementException( "Start vertex not found" );
11
12 clearAll( );
13 start.pos = pq.insert( new Path( start, 0 ) ); start.dist = 0;
14
15 while ( !pq.isEmpty( ) )
16 {
17 Path vrec = pq.deleteMin( );
18 Vertex v = vrec.dest;
19
20 for( Edge e : v.adj )
21 {
22 Vertex w = e.dest;
23 double cvw = e.cost;
24
25 if( cvw < 0 )
26 throw new GraphException( "Graph has negative edges" );
27
28 if( w.dist > v.dist + cvw )
29 {
30 w.dist = v.dist + cvw;
31 w.prev = v;
32
33 Path newVal = new Path( w, w.dist );
34 if( w.pos == null )
35 w.pos = pq.insert( newVal );
36 else
37 pq.decreaseKey( w.pos, newVal );
38 }
39 }
40 }
41 }
figure 23.16
Dijkstra's algorithm, using the pairing heap and the decreaseKey operation
rather than repeatedly calling deleteMin until an unseen vertex emerges.
Consequently, we no longer need the scratch data member. Compare lines
15-18 to the corresponding code presented in Figure 14.27. All that remains