CP 312: Algorithms
Module 6: Graph Algorithms
Eugene Zima
Text readings: CLRS, (sections 24.1, 25.2)
Wilfrid Laurier University
Winter 2025
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 1 / 12
Single-source shortest path
d(ℓ, j) = Length of shortest path from s to j that uses at
most ℓ edges.
d(0, j) = 0 if j = s and ∞ otherwise.
d(ℓ, j) = min d(ℓ − 1, j), mink {d(ℓ − 1, k) + wkj }
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 2 / 12
Single-source shortest path
This gives rise to an obvious DP algorithm:
for i = 1..n: d[i] = ∞
d[s] = 0
for ℓ = 1..n − 1:
for j = 1..n:
for k = 1..n:
d[j] = min(d[j], d(k) + wkj )
Which runs in Θ(n3 ) time.
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 3 / 12
Single-source shortest path
Runtime can be improved by only looking at the (j, k) pairs
corresponding to edges; this makes Θ(n|E |) runtime.
Worse than Dijkstra, but works for negative-length edges.
This is the Bellman-Ford algorithm (Chapter 24.1; the book
explains it different and before APSP)
(From the 1950’s ...)
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 4 / 12
All-pairs shortest path
Given a directed graph with edge lengths wi,j , for each
ordered pair of vertices (u, v ), compute δ(u, v ) (shortest path
from u to v )
If edge lengths are nonnegative, can use Dijkstra’s algorithm n
times (treat each vertex as source)
This costs Θ(n(m + n log n)) with best possible
implementation of Dijkstra’s algorithm
What if we permit negative lengths?
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 5 / 12
First try
If a graph has a negative cycle, then shortest paths are not
well-defined
The shortest path from u to v with at most one edge is the
edge (u, v ) of length wu,v
Define distfirst(u, v , k) to be the length of the shortest path
from u to v with at most k edges
Can we come up with a recurrence?
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 6 / 12
First try recurrence
(
wu,v k=1
distfirst(u, v , k) =
mint {distfirst(u, t, k − 1) + wt,v } k > 1
This works since optimal k-edge path contains an optimal
(k − 1)-edge path
Answers are distfirst(u, v , n − 1)
Order of computation is by increasing k
Each entry takes Θ(n) time to compute, and there are Θ(n3 )
entries
Total running time is Θ(n4 ) - not very good
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 7 / 12
Second try: find middle
A shortest k-edge path from u to v has some middle vertex m
The sections of the paths from u to m and from m to v are
[k/2]-edge shortest paths
Define distmid(u, v , j) to be the length of the shortest path
from u to v with at most 2j edges
Can define distmid(u, v , j) in terms of distmid(∗, ∗, j − 1)
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 8 / 12
Second try recurrence
(
wu,v n j =0
distmid(u, v , j) = o
minm distmid(u, m, j − 1) + distmid(m, v , j − 1) j >0
Answers are distmid(u, v , [log n])
Order of computation is by increasing j
Each entry takes Θ(n) time to compute, and there are
Θ(n2 log n) entries
Total running time is Θ(n3 log n) - better
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 9 / 12
Third try: add a vertex
Use idea from Dijkstra (and Prim) of adding one vertex at a
time to a set and maintaining shortest paths within that set
Consider a shortest path P from u to v whose internal
vertices are in the set {1, 2, · · · , k}
If vertex k is in the path, it splits P into paths from u to k
and from k to v
Both of these have internal vertices from {1, 2, · · · , k − 1}
Define distset(u, v , k) to be the length of the shortest path P
mentioned above
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 10 / 12
Third try recurrence
wu,v
k=0
distset(u, v , k) = distset(u, k, k − 1) + distset(k, v , k − 1),
min
k>0
distset(u, v , k − 1)
Answers are distset(u, v , n)
Order of computation is by increasing k
Each entry takes Θ(1) time to compute, and there are Θ(n3 )
entries
Total running time is Θ(n3 ) - best
Can be implemented in n2 space
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 11 / 12
Pseudocode for Floyd-Warshall
D←W
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
D[i, j] = min(D[i, j], D[i, k] + D[k, j])
E. Zima (WLU) Module 7: Graph Algorithms Winter 2025 12 / 12