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

1 /**
2 * Single-source negative-weighted acyclic-graph shortest-path algorithm.
3 */
4 public void acyclic( String startName )
5 {
6 Vertex start = vertexMap.get( startName );
7 if( start == null )
8 throw new NoSuchElementException( "Start vertex not found" );
9
10 clearAll( );
11 Queue<Vertex> q = new LinkedList<Vertex>( );
12 start.dist = 0;
13
14 // Compute the indegrees
15 Collection<Vertex> vertexSet = vertexMap.values( );
16 for( Vertex v : vertexSet )
17 for( Edge e : v.adj )
18 e.dest.scratch++;
19
20 // Enqueue vertices of indegree zero
21 for( Vertex v : vertexSet )
22 if( v.scratch == 0 )
23 q.add( v );
24
25 int iterations;
26 for( iterations = 0; !q.isEmpty( ); iterations++ )
27 {
28 Vertex v = q.remove( );
29
30 for( Edge e : v.adj )
31 {
32 Vertex w = e.dest;
33 double cvw = e.cost;
34
35 if( --w.scratch == 0 )
36 q.add( w );
37
38 if( v.dist == INFINITY )
39 continue;
40
41 if( w.dist > v.dist + cvw )
42 {
43 w.dist = v.dist + cvw;
44 w.prev = v;
45 }
46 }
47 }
48
49 if( iterations != vertexMap.size( ) )
50 throw new GraphException( "Graph has a cycle!" );
51 }
figure 14.32
A shortest-path algorithm for acyclic graphs