Introduction To Algorithms CS 445This LectureJohnson’s AlgorithmChoosing reweighting functionJohnson’s algorithmExampleFlow networksFormalizationMaximum flowAugmenting pathThe Ford-Fulkerson methodResidual networkResidual capacity of a pathSlide 14CutsCorrectness of Ford-FulkersonEdmonds-Karp algorithmMaximum Bipartite MatchingSlide 19Slide 20Solving the Maximum Bipartite Matching ProblemCorresponding Flow NetworkSlide 23Introduction To AlgorithmsCS 445Discussion Session 8Instructor: Dr Alon EfratTA : Pooja Vaswani04/04/20052This Lecture•All-pairs shortest paths–Johnson’s algorithm•Maximum flow–Concepts–Ford-Fulkerson method–Maximum bipartite matching3Johnson’s Algorithm•What if the graph is sparse?–If no negative edges – run repeated Dijkstra’s–If negative edges – let us somehow change the weights of all edges (to w’) and then run repeated Dijkstra’s•Requirements for reweighting:–Non-negativity: for each (u,v), w’(u,v) 0–Shortest-path equivalence: for all pairs of vertices u and v, a path p is a shortest path from u to v using weights w if and only if p is a shortest path from u to v using weights w’.4Choosing reweighting function•How to choose function h?•The idea of Johnson:–1. Augment the graph by adding vertex s and edges (s,v) for each vertex v with 0 weights.2. Compute the shortest paths from s in the augmented graph (using Belman-Ford).3. Make h(v) = (s, v) 1-1-1-230000s5Johnson’s algorithm•Why does it work?–By definition of the shortest path: for all edges (u,v), h(u) h(v) + w(u,v)–Thus, w(u,v) + h(u) – h(v) 0•Johnson’s algorithm:–1. Construct augmented graph–2. Run Bellman-Ford (possibly report a negative cycle), to find h(v) = (s, v) for each vertex v–3. Reweight all edges: •w’(u,v)  w(u,v) + h(u) – h(v).–4. For each vertex u:•Run Dijkstra’s from u, to find ’(u, v) for each v•For each vertex v: D[u][v] ’(u, v) + h(v) – h(u)6Example•Do the reweighting on this example:7Flow networks•What if weights in a graph are maximum capacities of some flow of material?–Pipe network to transport fluid (e.g., water, oil)•Edges – pipes, vertices – junctions of pipes–Data communication network •Edges – network connections of different capacity, vertices – routers (do not produce or consume data just move it)–Concepts (informally): •Source vertex s (where material is produced)•Sink vertex t (where material is consumed)•For all other vertices – what goes in must go out•Goal: maximum rate of material flow from source to sink8Formalization•How do we formalize flows?–Graph G=(V,E) – a flow network•Directed, each edge has capacity c(u,v)  0•Two special vertices: source s, and sink t•For any other vertex v, there is a path s…v…t–Flow – a function f : V V R•Capacity constraint: For all u, v  V: f(u,v) c(u,v)•Skew symmetry: For all u, v  V: f(u,v) = –f(v,u)•Flow conservation: For all u  V – {s, t}:, or( , ) ( , ) 0( , ) ( , ) 0v Vv Vf u v f u Vf v u f V u  9Maximum flow•What do we want to maximize?–Value of the flow f: ( , ) ( , ) ( , )v Vf f s v f s V f V t  We want to find a flow of maximum value!131154151014193st9abcd513386108210Augmenting path•Idea for the algorithm:–If we have some flow,…–…and can find a path p from s to t (augmenting path), such that there is a > 0, and for each edge (u,v) in p we can add a units of flow: f(u,v) + a c(u,v)–Then just do it, to get a better flow!–Augmenting path in this graph? 131154151014193st9abcd513386108211The Ford-Fulkerson methodFord-Fulkerson(G,s,t) 01 initialize flow f to 0 everywhere02 while there is an augmenting path p do03 augment flow f along p04 return f•Sketch of the method:How do we find augmenting path?How much additional flow can we send through that path?Does the algorithm always find the maximum flow?12Residual network•How do we find augmenting path?–It is any path in residual network:•Residual capacities: cf(u,v) = c(u,v) – f(u,v)•Residual network: Gf=(V,Ef), where Ef = {(u,v)  V V : cf(u,v) > 0}•What happens when f(u,v) < 0 (and c(u,v) = 0)?•Observation – edges in Ef are either edges in E or their reversals: |Ef| 2|E|Compute residual network:131154151014193st9abcd513386108213Residual capacity of a path•How much additional flow can we send through an augmenting path?–Residual capacity of a path p in Gf:cf(p) = min{cf(u,v): (u,v) is in p}–Doing augmentation: for all (u,v) in p, we just add this cf(p) to f(u,v) (and subtract it from f(v,u))–Resulting flow is a valid flow with a larger value. –What is the residual capacity of the path (s,a,b,t)?14The Ford-Fulkerson methodFord-Fulkerson(G,s,t) 01 for each edge (u,v) in G.E do 02 f(u,v) f(v,u)  0 03 while there exists a path p from s to t in residual network Gf do04 cf = min{cf(u,v): (u,v) is in p} 05 for each edge (u,v) in p do06 f(u,v) f(u,v) + cf07 f(v,u)  -f(u,v)08 return fThe algorithms based on this method differ in how they choose p in step 03.15Cuts –A cut is a partition of V into S and T = V – S, such that s S and t T–The net flow (f(S,T)) through the cut is the sum of flows f(u,v), where u S and v T–The capacity (c(S,T)) of the cut sum of capacities c(u,v), where u S and v T–Minimum cut – a cut with the smallest capacity of all cuts–|f|= f(S,T)Does it always find the maximum flow?131154151014193st9abcd5133861091116Correctness of Ford-Fulkerson•Max-flow min-cut theorem:–If f is the flow in G, the following conditions are equivalent:•1. f is a maximum flow in G•2. The residual network Gf contains no augmenting paths•3. |f| = c(S,T) for some cut (S,T) of G17Edmonds-Karp algorithm•Take shortest path (in terms of number of edges) as an augmenting path – Edmonds-Karp algorithm–How do we find such a shortest path?–Running time O(VE2), because the number of augmentations is O(VE)–To prove this we need to prove that:•The length of the shortest path does not decrease•Each edge can become critical at most ~ V/2 times. Edge (u,v) on an augmenting path p is critical if it has the minimum residual capacity in the path: cf(u,v) = cf(p)18Maximum Bipartite MatchingA bipartite graph is