Graph Algorithms 2 COMP 465 – Algorithm Design Techniques Denis Pankratov Last time Basic graph terminology Representations of graphs: adjacency matrix and adjacency lists BFS, DFS Topological sort Strongly connected components MST: generic algorithm, Kruskal’s and Prim’s algorithms Shortest paths: types of problems, single-source shortest paths with non-negative weights, Dijkstra’s algorithm Shortest paths Edge-weighted graph = , , ∶ → Weight of path = !, “, … , # is = ∑$%”# $&”, $ = sum of edge weights on Shortest-path weight to : , = 2min ∶ →’ if there is a path from to ∞ otherwise Can think of weights as representing any measure that accumulates linearly along a path and we wish to minimize it Variants of shortest paths problems Single-source Find shortest paths from a given source vertex ∈ to every vertex ∈ Single-destination Find shortest paths to a given destination vertex Single-pair Find shortest path from to . Not known how to do it faster than single- source. All-pairs Find shortest path from to for all , ∈ . Negative-weight edges Some algorithms will not work when negative-weight edges are present Other algorithms will work with negative-weight edges so long as there are no negative-weight cycles reachable from the source If we have a negative-weight cycle, we can just keep going around it, and get , = ∞ for all on the cycle Some algorithms allow one to detect presence of negative-weight cycles Some properties of shortest paths Optimal substructure property Any subpath of a shortest path is a shortest path itself No cycles property Shortest paths do not contain cycles without loss of generality Triangle inequality For all , ∈ we have , ≤ , + , Single-source shortest paths (CLRS 24) Input: = , , ∶ → source vertex ∈ Output: for each vertex populate attribute . = (, ) for each vertex populate attribute . = predecessor of on shortest path from Generic algorithm Initially set . ← ∞ As an algorithm progresses, . reduces but satisfies . ≥ (, ) Call . a shortest path estimate Initially set . ← The predecessor graph . , forms a tree called shortest-path tree Shortest path estimate is improved by relaxing an edge Generic algorithm( = (, ), ) ∈ . ← ∞. ← . ← 0 (, , ) // (, ) is an edge // is the weight function . > . + (, ). ← . + (, ). ← All single-source shortest paths algorithms we consider Start by calling Then relax edges Algorithms differ in the order and number of times edges are relaxed Upper bound property Always have . ≥ (, ) for all ∈ Path relaxation property If = !, “, … , # is a shortest path from ! = to = #. If we relax edges in order !, ” , “, $ , … , (#%”, #) even intermixed with other relaxations then we get . = (, ) Bellman-Ford Algorithm Allows negative-weight edges Returns if no negative-weight cycles are reachable from , otherwise( = , , , )(, ) = 1 1 , ∈ (, , ) , ∈ . > . + (, ) Main idea: relax each edge 1 times Running time: Θ 1 3 4 1 2 2 35 1 3 4 1 2 2 3 . = . = 0 . = . = ∞ . = . = ∞ . = . = ∞ . = . = ∞ 5 1 3 4 1 2 2 3 1st round . = . = 0 . = . = ∞ . = . = 4 . = . = 1 . = . = ∞ Relax edges in order:, , , , , , , , , (, ), , (, ) 5 1 3 4 1 2 2 3 . = . = 0 . = . = 1 . = . = 2 . = . = 1 . = . = 1 Relax edges in order:, , , , , , , , , (, ), , (, ) 5 2nd round 1 3 4 1 2 2 3 . = . = 0 . = . = 1 . = . = 2 . = . = 1 . = . = 2 Relax edges in order:, , , , , , , , , (, ), , (, ) 5 3rd round Bellman-Ford algorithm solves single-source shortest paths correctly Proof Suppose = !, “, … , # is a shortest path from = ! to = # By the no cycles property, is acyclic and therefore has ≤ 1 edges Each iteration of the outer loop relaxes all edges: First iteration guarantees to relax !, ” Second iteration guarantees to relax “, ( th iteration guarantees to relax #&”, # By the path relaxation property, . = , proof continued What about / values returned by the algorithm 1. Suppose there is no negative-weight cycle reachable from At termination for all , ∈ . = , ≤ , + , (by triangle inequality)= . + (, ) 2. Suppose there is a negative-weight cycle reachable from Let the cycle be !, “, … , # Assume
for contradiction that Bellman-Ford returns t$%”# $ . ≤t$%”# $&”.
+ $&”, $ =t$%”# $&”. +t$%”# $&”, $ Observe that ∑$%”# $ . = ∑$%”# $&”. , therefore ∑$%”# $&”, $ ≥ 0 Contradiction. All-pairs shortest paths (CLRS 25) Input: = , , ∶ → Output: × matrix = $) of shortest distances $) = (, ) Could run Bellman-Ford from each vertex: running time is ( which is ||* for dense graphs, i.e., = Θ ||( If weights are non-negative, could run Dijkstra’s from each vertex: running time is log with binary heap which is + log if dense We can achieve + in all cases with no fancy data structures Shortest paths and matrix multiplication Record input weights in a matrix = $)$) = 0 = , ≠ , , ∈ ∞ ≠ , , This matrix has interpretation:$) = weight of a shortest path from to that uses at most 1 edge To compute weights of shortest paths that use 2 edges Shortest path from to using 2 edges: either uses a shortest path from to with at most 1 edge or uses an intermediate node and uses shortest path from to with at most 1 edge and shortest path from to with at most 1 edge Denote the resulting matrix by (() = $)( Can be computed as$)( = min($) , min# ($# +#))) Note: this is like matrix-multiplication with replaced by + and ∑ replaced by min Similarly can compute shortest paths that use at most 3, 4, … edges By the no cycle property, it suffices to compute shortest paths that use at most 1 edges Need
to compute . &” . First attempt: () ” ← = 2 1 ‘ ← new ×
matrix, initially filled with ∞ ∈ ∈ ∈ $)’ ← min $)’ ,$#’&”
+#)’&” . &” Running time: Θ & Can speed it up with repeated squaring Can compute ” , ( , * , / , “0 , … , 1 Until > 1 It’s okay to overshoot, since 1 doesn’t change after ≥ 1 Since is doubled every time, the outer loop is executed at most log || times Overall running time becomes + log Can speed it up with repeated squaring () ” ← ← 1 < 1($() ← new × matrix, initially filled with ∞ ∈ ∈ ∈ *+$( ← min *+$( ,*#( +#+( ← 2 ( Floyd-Warshall algorithm A different dynamic programming algorithm Assume = [] for simplicity For a path = !, ", … , # an intermediate vertex is any vertex except for ! and # Define$)# = shortest path weight of any path → with all intermediate vertices in {1, 2, … } This is the semantic array for the DP The overall answer is 2 = $)2 Consider a shortest path →' with all intermediate vertices in 1, 2, … , If is not an intermediate vertex then all intermediate vertices are in {1, 2, … , 1} If is an intermediate vertex: Computational array:$)# = 2$) = 0min $)#&" , $##&" + #)#&" ≥ 1 Pseudocode
for Floyd-Warshall (, ) ! ← = 1 || # ← new || × || matrix = 1 ||
= 1 ||$)# ← min $)#&" , $##&" + #)#&" 2 Running time: Θ , Maximum flow = (, ) is directed Source vertex and sink vertex Each edge (, ) has capacity , ≥ 0 If , then , = 0 If , ∈ then , (can work around this restriction) Assume for all ∈ there exists a path from to and from to The goal is to send maximum amount of flow from to 2 3 31 2 3 2 3 3 Flow A function ∶ × → Capacity constraint: for all , ∈ 0 ≤ , ≤ , Flow conservation: for all ∈ , t3∈. (, ) = t3∈. (, ) 2 3 31 2 3 2 3 3 2/2 2/3 1/31/1 2/2 2/3 1/2 1/3 1/3 capacityflow 2/2 2/3 1/31/1 2/2 2/3 1/2 / / Flow into = 2 / 2/3 1/31/1 2/2 2/3 1/2 / / Flow into = 2 Flow out of = 2 / 2/3 /1/1 2/2 2/3 1/2 1/3 1/3 Flow into = 3 / 2/3 // 2/2 / 1/2 1/3 1/3 Flow into = 3 Flow out of = 3 2/2 2/3 1/31/1 2/2 2/3 1/2 1/3 1/3 Flow into = 3 Flow out of = 3 2/2 2/3 1/31/1 2/2 2/3 1/2 1/3 1/3 Flow into = 2 Flow out of = 2 Value of flow and maximum flow problem Value of flow = = ∑3∈. , ∑3∈. , = flow out of source flow into source Input: = , , ∈ , ∈ , ∶ × → 5! Output: flow ∶ × →
such that | | is maximized Antiparallel edges Edges , and , are called antiparallel If = (, ) contains antiparallel edges we can modify it into an equivalent graph (preserving maximum flow value) without antiparallel edges: ′ Introduce new node ′ Cuts A cut , of flow network is a partition of into and = such that ∈ and ∈ Similar to a cut in MSTs, except is directed and we require ∈ and ∈ Given ∶ × → the net flow across cut , is , = t6∈7t3∈8 , t6∈7t3∈8 , Capacity of the cut is , = t6∈7t3∈8 , Minimum cut is a cut whose capacity is minimum over all cuts Asymmetry between flow and cut Given cut (, ) note that for net flow take flow of edges from to and subtract flow of edges from to for capacity of the cut take capacity of edges only going from to 2/2 2/3 1/31/1 2/2 2/3 1/2 1/3 1/3 , = , + , , = 3 , = , + , = 5 Lemma: For any cut (, ) we have , = || Proof: We need to show that , = t6∈7,3∈8 (, ) t6∈7,3∈8 , is equal to = t3∈. (, ) t3∈. , Conservation constraint: ∈ {}: ∑3∈. (, ) ∑3∈. , = 0 Therefore: t6∈7& : t3∈. , t3∈. , = 0 Add
it to the definition of ||: = t3∈. (, ) t3∈. , + t6∈7& : t3∈. ,
t3∈. , = t6∈7,3∈. (, ) t6∈7,3∈. , = t6∈7,3∈8 (, ) t6∈7,3∈8 , +
t6∈7,3∈7 , t6∈7,3∈7 , = (, ) = 0 QED Corollary: The value of any flow is at most the capacity of any cut. Proof: Let be an arbitrary flow, and , be an arbitrary cut. By previous lemma we have: = , = t6∈7,3∈8 , t6∈7,3∈8 , ≤ t6∈7,3∈8 , ≤ t6∈7,3∈8 , = , QED Ford-Fulkerson method A framework for solving the maximum flow problem Not a specific algorithm A famous algorithm based on this framework is Edmonds-Karp The method builds on two types of objects: Residual network and Augmenting paths Ford-Fulkerson method Idea: start with all 0-flow and increase it as follows: Find a path from to that allows additional flow to be sent along without violating capacity constraints Send additional flow along Repeat as long as possible Residual network: helps identify possible paths along which to send additional flow Augmenting path: a specific path as above Residual network Given current flow and a pair of vertices and , how much additional flow can we push directly from to This is called residual capacity, denoted by ; , : ; , = , , , ∈ , , ∈ 0 , , , The residual network is = (, where; = , ∈ × ∶ ; , > 0 122 1 2 with flow : 1 12 2 1 1 1 12 2 Residual network ;: Residual network properties Each edge , ∈ ; corresponds to , ∈ or , ∈ , thus:; ≤ 2 Residual network can contain antiparallel edges , , , ∈ ; Can define a flow in residual network that satisfies the definition but with respect to residual capacities ; , Augmentation Given flows in and < in ; define augmentation of by ′, denoted by ↑ < : ↑ < , = , + < , < , , ∈ 0 , Intuition: Increase (, ) by < , Decrease it by < , because pushing flow in reverse cancels some of the flow in the original network Augmenting path Simple path from to in ; It allows us to push more flow from to How much more flow It is restricted by the minimum residual capacity along the path, i.e.; = min ; , ∶ , is on path 122 1 2 with flow : 1 12 2 1 1 1 12 2 Residual network ;: 2 1 2 with flow : 1 2 1 1 1 2 2 Residual network ;: Augmenting path = , , , , , Minimum residual capacity along ; = 1 with flow : Residual network ; and augmenting path 3/3 2/31/1 2/2 3/3 1/2 2/3 0/3 2/2 After pushing 1 unit of flow along the augmenting path: Residual graph after pushing 1 unit of flow along the augmenting path: 3 2 1 3 1 2 1 1 321 2 No augmenting path. We claim that the flow is maximum Lemma: given flow network , flow in , and an augmenting path in residual graph ;. Define ' ∶ × → '(, ) = ; if , is on 0 otherwise Then ' is a flow in ; with value ' = ; > 0. Corollary: ↑ ‘ is a flow in with value ↑ ‘ = + ‘ > || Max-flow min-cut theorem The following are equivalent:1. is a maximum flow2. ; has no augmenting path3. = , for some cut , Proof:1 2: show contrapositive if ; has an augmenting path then is not maximum, since ↑ ‘ is a flow of bigger value than . Max-flow min-cut theorem The following are equivalent:1. is a maximum flow2. ; has no augmenting path3. = , for some cut , Proof:2 3: suppose ; has no augmenting path. Define: = ∈ ∶ there exists a path from to in ; = We have ∈ since otherwise there is an augmenting path Therefore (, ) is a valid cut Max-flow min-cut theorem The following are equivalent:1. is a maximum flow2. ; has no augmenting path3. = , for some cut , Proof:2 3: … continued. For ∈ and ∈ , ∈ implies that , = , (why ) , ∈ implies that , = 0 (why ) , , , implies that , = , = 0 Max-flow min-cut theorem The following are equivalent:1. is a maximum flow2. ; has no augmenting path3. = , for some cut , Proof:2 3: … continued. = , = t6∈7,3∈8 (, ) t3∈8,6∈7 , = t6∈7,3∈8 , t3∈8,6∈7 0 = (, ) Max-flow min-cut theorem The following are equivalent:1. is a maximum flow2. ; has no augmenting path3. = , for some cut , Proof:3 1: If = , and for any flow ′ we have < ≤ (, ) (by one of the previous corollaries). Therefore is maximum flow. Ford-Fulkerson method Keep augmenting flow along an augmenting path until there is no augmenting path. Represent flow in an attribute , . ( = (, ), , ) , ∈ , . ← 0 there is an augmenting path in ; augment by ' If capacities are all integers each augmenting path raises the value of flow by at least 1. Let denote a max flow then Ford-Fulkerson method needs at most | | iterations. The running time is . This running time is not polynomial since is not a function of and . If capacities are rational then they can be scaled to integers. If capacities are irrational then this method might never terminate! Integrality theorem If the capacity function takes on only integer values then the maximum flow produced by the Ford-Fulkerson method has the property that is an integer. Moreover for all vertices , the value , is an integer. Edmonds-Karp algorithm Perform but to compute augmenting paths run BFS in ; Augmenting paths are shortest unweighted paths in ; Theorem: Edmonds-Karp performs augmentations Thus, the overall running time is ( See the book for details. Bipartite graphs An undirected graph = , is bipartite if we can partition the set of vertices = ∪ such that all edges go between and 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 bipartite A matching is a subset of edges such that no two edges from share a common vertex, i.e., for all ", ( ∈ we have " ∩ ( = A matching of maximum size is called a maximum matching. 1 2 3 4 5 6 7 8 9 A matching 1 2 3 4 5 6 7 8 9 A maximum matching Maximum matching problem Input: given undirected bipartite graph = (, ) with bipartition = ∪ Output: a maximum matching Given a bipartite define flow network < = <, < as follows: < = ∪ , < = , ∶ ∈ ∪ , ∶ ∈ , ∈ , , ∈ ∪, ∶ ∈ , = 1 for all , ∈ < 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0/1 0/10/10/10/10/1 0/10/1 0/10/10/10/1 0/1 0/1 0/10/10/1 Find an integral max flow Include those edges , that have ∈ and ∈ and , = 1 1 2 3 4 5 6 7 8 9 0/1 0/1//0/1/ /0/1 /0/10/10/1 / / //0/1 Running time is See the book for details Now you should be able to… Solve single-source shortest paths on general weighted graphs (with negative edges and possibly even negative cycles) Solve all-pairs shortest paths using either matrix multiplication or Floyd-Warshall. Understand how to speed up matrix multiplication approach using repeated squaring Describe flow networks, state defining properties of flows, residual graphs, augmenting paths Explain method and Edmonds-Karp algorithm. Explain the difference between the two Apply network flow algorithms to solve the maximum matching problem Review questions Write down pseudocode for Bellman-Ford, APSP matrix multiplication, Floyd-Warshall Write down pseudocode for Edmonds-Karp Write down pseudocode for solving the maximum matching algorithm State the max-flow and min-cut theorem and the integrality theorem