COMP 465 – Algorithm Design Techniques
Algorithm Design Techniques
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP 465 – Algorithm Design Techniques
• 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: Θ ⋅
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