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

1 /**
2 * Single-source negative-weighted shortest-path algorithm.
3 */
4 public void negative( String startName )
5 {
6 clearAll( );
7
8 Vertex start = vertexMap.get( startName );
9 if( start == null )
10 throw new NoSuchElementException( "Start vertex not found" );
11
12 Queue<Vertex> q = new LinkedList<Vertex>( );
13 q.add( start ); start.dist = 0; start.scratch++;
14
15 while( !q.isEmpty( ) )
16 {
17 Vertex v = q.removeFirst( );
18 if( v.scratch++ > 2 * vertexMap.size( ) )
19 throw new GraphException( "Negative cycle detected" );
20
21 for( Edge e : v.adj )
22 {
23 Vertex w = e.dest;
24 double cvw = e.cost;
25
26 if( w.dist > v.dist + cvw )
27 {
28 w.dist = v.dist + cvw;
29 w.prev = v;
30 // Enqueue only if not already on the queue
31 if( w.scratch++ % 2 == 0 )
32 q.add( w );
33 else
34 w.scratch--; // undo the enqueue increment
35 }
36 }
37 }
38 }
figure 14.29
A negative-weighted, shortest-path algorithm: Negative edges are allowed.
enqueue it. However, we do not add 2 to it to indicate that it has gone on (and off)
the queue; this is done by offsetting of lines 31 and 34. The rest of the algorithm
uses code that has already been introduced in both the unweighted shortest-path
algorithm (Figure 14.22) and Dijkstra's algorithm (Figure 14.27).