CSCI-SHU 220: Algorithms
Shortest Paths with Weights
NYU Shanghai
Spring 2025
CSCI-SHU 220: Algorithms 1 / 29
Bipartite Matching
A bipartite (undirected) graph G = (V , E ), and V can be divided into
two disjoint blocks X and Y such that no edge connects a vertex in
X and a vertex in Y .
A matching M ⊆ E , is a set of edges such that do not share any
endpoints.
Maximal matching: a matching that is not a subset of any other
matching.
Maximum matching: a matching of the largest cardinality.
CSCI-SHU 220: Algorithms 2 / 29
Bipartite Matching
An alternating path given a matching M is a (simple) path in which
the edges alternately belong/ do not belong to the matching M.
An augmenting path given a matching M is an alternating path
whose beginning and ending edges are not in the matching M.
Lemma (Berge’s Lemma)
A matching M is maximum iff there is no augmenting path given the
matching M.
CSCI-SHU 220: Algorithms 3 / 29
Bipartite Matching
Kuhn’s Algorithm.
M := ∅
For v ∈ X :
DFS on v to find an augmenting path.
Add the path to M.
CSCI-SHU 220: Algorithms 4 / 29
Bipartite Matching
Hopcroft-Karp Algorithm
M := ∅
While True
Let X ′ ⊆ X be the set of vertices are not included in M.
Run BFS on X ′ until we reach a set Y ′ ⊆ Y of vertices that are not
included in M. The BFS levels have to alternate between unmatched
and matched edges.
if Y ′ is empty after BFS finishes, break the while loop.
CSCI-SHU 220: Algorithms 5 / 29
Bipartite Matching
Hopcroft-Karp Algorithm
M := ∅
While True
Let X ′ ⊆ X be the set of vertices are not included in M.
Run BFS on X ′ until we reach a set Y ′ ⊆ Y of vertices that are not
included in M. The BFS levels have to alternate between unmatched
and matched edges.
if Y ′ is empty after BFS finishes, break the while loop.
For every v ∈ Y ′ (iteratively one-by-one), run DFS based on the BFS
result: we only go up a level for every edge in DFS, and we have to
alternate between unmatched and matched edges. DFS stops if we
reach a vertex in X ′ .
Add the DFS result to M if succeeded in reaching v ′ ∈ X ′ . Remove
vertex v ′ from X ′ .
CSCI-SHU 220: Algorithms 5 / 29
Bipartite Matching
Hopcroft-Karp Algorithm Analysis
√
O(m n).
CSCI-SHU 220: Algorithms 6 / 29
Various shortest-path problems
Classification according to source/target
s-t shortest path
Single-source shortest paths (SSSP)
All-pair shortest paths (APSP)
Classification according to graph type
Undirected
Directed
Classification according to edge weights
Unweighted
Weighted
CSCI-SHU 220: Algorithms 7 / 29
Shortest paths
BFS can solve unweighted shortest-path problems.
s-t shortest path: O(n + m) time
SSSP: O(n + m) time
APSP: O(n(n + m)) time
Weighted shortest-path problems
Every edge ⟨u, v ⟩ has a weight P w (u, v ) ∈ R. The length of a path
(v0 , v1 , . . . , vr ) is defined as ri=1 w (vi−1 , vi ).
In the simplest setting, the weights are non-negative (or positive).
In directed graphs, sometimes we allow negative edges. But negative
cycles are not allowed.
CSCI-SHU 220: Algorithms 8 / 29
Shortest paths
Weighted s-t shortest path and weighted SSSP
Theorem (Dijkstra’s algorithm)
SSSP with non-negative weights in undirected/directed graphs can be
solved in O(n log n + m) time, where n = |V | and m = |E |.
What if negative edges are allowed? (W = maximum weight)
Bellman–Ford algorithm (1955): O(nm) time
Nanongkai and Wulff-Nilsen (2021): O(m log8 n log W ) time
(https://arxiv.org/abs/2203.03456)
Bringmann et al. (2023): O(m log2 n log log n log W ) time
(https://arxiv.org/abs/2304.05279)
CSCI-SHU 220: Algorithms 9 / 29
Dijkstra’s Algorithm
Single Source Shortest Path (SSSP).
Positive weights w : E → R>0 .
Key idea:
For a path s, v1 , v2 , . . . , vr , t to be a s − t shortest path, then stopping
at any vi gives an s − vi shortest path.
Build the shortest paths greedily, i.e., add one vi at a time.
CSCI-SHU 220: Algorithms 10 / 29
Dijkstra’s Algorithm
Algorithm Steps:
Let X := {s}, Y := V \ {s}
While |Y | > 0
du := minv ∈X ∩N(u) (dist[v ] + w (v , u)) for all u ∈ Y .
u ∗ := arg minu∈Y du
dist[u ∗ ] := du∗
Move u ∗ from Y to X .
CSCI-SHU 220: Algorithms 11 / 29
Dijkstra’s Algorithm
Proof:
For any u ∈ V , dist[u] ≥ d(s, u).
If u ′ is added to X later than u, dist(u) ≤ dist(u ′ ).
At any time, for any t ∈ X , dist[t] = d(s, t).
CSCI-SHU 220: Algorithms 12 / 29
Dijkstra’s Algorithm
The naive implementation takes O(n2 ) time.
For O(n log n + m), we need to use a Fibonacci heap (beyond our
scope). It allows O(1) findMin, decreaseKey and log(n) deleteMin
(amortized).
CSCI-SHU 220: Algorithms 13 / 29
Shortest paths
Weighted APSP
Can be solved by applying a SSSP algorithm n times.
Dijkstra: O(n2 log n + nm) time =⇒ O(n3 ) time in worst case
(Cons: can’t handle negative edges)
Others: ω(n3 ) time in worst case (but can handle negative edges)
Floyd algorithm (or Floyd–Warshall algorithm)
Solving APSP (both undirected/directed) in O(n3 ) time
Allowing negative edges (but not negative cycles)
Based on dynamic programming
CSCI-SHU 220: Algorithms 14 / 29
All-pair shortest paths
Let’s try to solve APSP using DP...
Suppose V = {v1 , . . . , vn } and w (vi , vj ) = ∞ for all ⟨vi , vj ⟩ ∈
/ E.
Pi,j = computing a shortest path from vi to vj
opt(Pi,j ) = mink∈{1,...,n},vk ∈N(vj ) (opt(Pi,k ) + w (vk , vj ))
What’s the issue here?
vj
vi
vj 0 vj 00
CSCI-SHU 220: Algorithms 15 / 29
All-pair shortest paths
Now we slightly modify the definition of subproblems.
A p-hop path is a path consisting of p edges. A (≤ p)-hop path is a
path consisting of at most p edges.
Pi,j,p = computing a shortest (≤ p)-hop path from vi to vj
opt(Pi,j,p ) = mink∈{1,...,n} (opt(Pi,k,p−1 ) + w (vk , vj ))
vi
vj
(≤ p)-hop
CSCI-SHU 220: Algorithms 16 / 29
All-pair shortest paths
Now we slightly modify the definition of subproblems.
A p-hop path is a path consisting of p edges. A (≤ p)-hop path is a
path consisting of at most p edges.
Pi,j,p = computing a shortest (≤ p)-hop path from vi to vj
opt(Pi,j,p ) = mink∈{1,...,n} (opt(Pi,k,p−1 ) + w (vk , vj ))
vi vk vj
(≤ p − 1)-hop
CSCI-SHU 220: Algorithms 17 / 29
All-pair shortest paths
Obtain a shortest path from vi to vj ?
Key observation
At least one shortest path is simple and thus (≤ n − 1)-hop.
vi
vj
vk
CSCI-SHU 220: Algorithms 18 / 29
All-pair shortest paths
Obtain a shortest path from vi to vj ?
Key observation
At least one shortest path is simple and thus (≤ n − 1)-hop.
vi
vj
vk
CSCI-SHU 220: Algorithms 19 / 29
All-pair shortest paths
Obtain a shortest path from vi to vj ?
Key observation
At least one shortest path is simple and thus (≤ n − 1)-hop.
vi
vj
vk
Removing a cycle can only increase the length
CSCI-SHU 220: Algorithms 20 / 29
All-pair shortest paths
The solution of Pi,j,n−1 is a shortest path from vi to vj .
APSP(G , w ) where G = (V , E ) and V = {v1 , . . . , vn }
opt[i, j, 0] ← ∞ for all different i, j ∈ {1, . . . , n}
opt[i, i, p] ← 0 for all i ∈ {1, . . . , n} and p ∈ {0, 1, . . . , n − 1}
for p = 1, . . . , n − 1 do
for (i, j) ∈ {1, . . . , n}2 such that i ̸= j do
opt[i, j, p] ← ∞
for k = 1, . . . , n do
if opt[i, k, p − 1] + w (vk , vj ) ≤ opt[i, j, p] then
opt[i, j, p] ← opt[i, k, p − 1] + w (vk , vj )
dist[i, j] ← opt[i, j, n − 1] for all i, j ∈ {1, . . . , n}
return dist[·, ·]
Time complexity = O(n4 )
CSCI-SHU 220: Algorithms 21 / 29
All-pair shortest paths
To do better?
Floyd algorithm uses a different idea to do DP.
vi Our idea:
How many hops?
vj
CSCI-SHU 220: Algorithms 22 / 29
All-pair shortest paths
To do better?
Floyd algorithm uses a different idea to do DP.
vi Floyd’s idea:
The largest index?
vj
CSCI-SHU 220: Algorithms 23 / 29
All-pair shortest paths
A k-route path is a path on which the internal vertices have indices at
most k, i.e., the internal vertices are in the set {v1 , . . . , vk }.
Pi,j,k = computing a shortest k-route path from vi to vj
Case 1: vk not on the path
vi
vj
CSCI-SHU 220: Algorithms 24 / 29
All-pair shortest paths
A k-route path is a path on which the internal vertices have indices at
most k, i.e., the internal vertices are in the set {v1 , . . . , vk }.
Pi,j,k = computing a shortest k-route path from vi to vj
Case 1: vk not on the path
vi
vj
(k − 1)-route
CSCI-SHU 220: Algorithms 25 / 29
All-pair shortest paths
A k-route path is a path on which the internal vertices have indices at
most k, i.e., the internal vertices are in the set {v1 , . . . , vk }.
Pi,j,k = computing a shortest k-route path from vi to vj
Case 2: vk on the path
vi
vk vj
CSCI-SHU 220: Algorithms 26 / 29
All-pair shortest paths
A k-route path is a path on which the internal vertices have indices at
most k, i.e., the internal vertices are in the set {v1 , . . . , vk }.
Pi,j,k = computing a shortest k-route path from vi to vj
Case 2: vk on the path
vi
vk vj
(k − 1)-route
CSCI-SHU 220: Algorithms 27 / 29
All-pair shortest paths
opt(Pi,j,k ) = min{opt(Pi,j,k−1 ), opt(Pi,k,k−1 ) + opt(Pk,j,k−1 )}
The solution of Pi,j,n is a shortest path from vi to vj .
This gives us an O(n3 )-time DP algorithm for APSP.
A trivial implementation requires O(n3 ) space.
Improve it to O(n2 )?
Key observation
opt(Pi,k,k ) = opt(Pi,k,k−1 ) and opt(Pk,j,k ) = opt(Pk,j,k−1 )
CSCI-SHU 220: Algorithms 28 / 29
All-pair shortest paths
FloydAPSP(G ) where G = (V , E ) and V = {v1 , . . . , vn }
opt[i, j] ← w (i, j) for i, j ∈ {1, . . . , n}
for k = 1, . . . , n do
for (i, j) ∈ {1, . . . , n}2 do
if opt[i, j] > opt[i, k] + opt[k, j] then
opt[i, j] ← opt[i, k] + opt[k, j]
return opt[·, ·]
Time complexity = O(n3 )
Question: How can we retrieve these shortest paths?
CSCI-SHU 220: Algorithms 29 / 29
