Ch9.3-4 Shortest-Path Algorithm, Network Flow Problem.ppt

§3 Shortest Path Algorithms 1. Single-Source Shortest-Path Problem Given as input a weighted graph, G = ( V, E ), and a distinguished vertex, s, find the shortest weighted path from s to every other vertex in G. Negative-cost cycle Note: If there is no negative-cost cycle, the shortest path from s to s is defined to be zero. 1/17 §3 Shortest Path Algorithms ? Unweighted Shortest Paths 0 0: ? v3 1: ? v1 and v6 1 1 2: ? v2 and v4 2 2 3: ? v5 and v7 3 3 ? Sketch of the idea Breadth-first search ? Implementation Table[ i ].Dist ::= distance from s to vi /* initialized to be ? except for s */ Table[ i ].Known ::= 1 if vi is checked; or 0 if not Table[ i ].Path ::= for tracking the path /* initialized to be 0 */ 2/17 §3 Shortest Path Algorithms void Unweighted( Table T ) { int CurrDist; Vertex V, W; for ( CurrDist = 0; CurrDist NumVertex; CurrDist ++ ) { for ( each vertex V ) if ( !T[ V ].Known T[ V ].Dist == CurrDist ) { T[ V ].Known = true; for ( each W adjacent to V ) if ( T[ W ].Dist == Infinity ) { T[ W ].Dist = CurrDist + 1; T[ W ].Path = V; } /* end-if Dist == Infinity */ } /* end-if !Known Dist == CurrDist */ } /* end-for CurrDist */ } The worst case: ? T = O( |V|2 ) If V is unknown yet has Dist Infinity, then Dist is either CurrDist or CurrDist+1. 3/17 §3 Shortest Path Algorithms ? Improvement void Unweighted( Table T ) { /* T is initialized with the source vertex S given */ Queue Q; Vertex V, W; Q = CreateQueue (NumVertex ); MakeEmpty( Q ); Enqueue( S, Q ); /* Enqueue the source vertex */ while ( !IsEmpty( Q ) ) { V = Dequeue( Q ); T[ V ].Known = true; /* not really necessary */ for ( each W adjacent to V ) if ( T[ W ].Dist == Infinity ) { T[ W ].Dist = T[ V ].Dist + 1; T[ W ].Path = V; Enqueue( W, Q ); } /* end-if Dist == Infinity */ } /* end-while */ DisposeQueue( Q ); /* free memory */ } 0 v3 v7 1 v3 v1 1 v3 v