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

1 /**
2 * Single-source weighted shortest-path algorithm.
3 */
4 public void dijkstra( String startName )
5 {
6 PriorityQueue<Path> pq = new PriorityQueue<Path>( );
7
8 Vertex start = vertexMap.get( startName );
9 if( start == null )
10 throw new NoSuchElementException( "Start vertex not found" );
11
12 clearAll( );
13 pq.add( new Path( start, 0 ) ); start.dist = 0;
14
15 int nodesSeen = 0;
16 while( !pq.isEmpty( ) && nodesSeen < vertexMap.size( ) )
17 {
18 Path vrec = pq.remove( );
19 Vertex v = vrec.dest;
20 if( v.scratch != 0 ) // already processed v
21 continue;
22
23 v.scratch = 1;
24 nodesSeen++;
25
26 for( Edge e : v.adj )
27 {
28 Vertex w = e.dest;
29 double cvw = e.cost;
30
31 if( cvw < 0 )
32 throw new GraphException( "Graph has negative edges" );
33
34 if( w.dist > v.dist + cvw )
35 {
36 w.dist = v.dist + cvw;
37 w.prev = v;
38 pq.add( new Path( w, w.dist ) );
39 }
40 }
41 }
42 }
figure 14.27
A positive-weighted, shortest-path algorithm: Dijkstra's algorithm
Each iteration of the while loop that begins at line 16 puts the eyeball at a
vertex v and processes it by examining adjacent vertices w . v is chosen by
repeatedly removing entries from the priority queue (at line 18) until we