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