EECS 477: Introduction to Algorithms Fall 209

Lecture 7 — Dynamic Programming on Shortest Path Problems

Prof. Seth Pettie Scribes: Lyndon Shi, Shang-En Huang

1 Background

A weighted graph G = (V, E, `) is defined by its vertices V (|V | = n, edges E (|E| = m, and length
function ` : E → R where `(e) = ∞ for e ∈/ E. Edges can be directed, meaning e = (u, v) is an edge
from u to v and there does not necessarily exist an edge (v, u).
A path P = (s, . . . , t) is a sequence of vertices such that no vertex is in the path twice, and there
exists an edge
P between each consecutive pair of vertices in the sequence. The length of P is given
by `(P ) = e∈P `(e) (e ∈ P means an edge required to traverse between consecutive vertices in
the path).
We are generally interested in the shortest path between two points. Hence, we define a distance
function, between vertices s and t, representing the length of the shortest path from s to t:

 min (`(P ))
dist(s, t) = P =(s,...,t)
∞ if @ an s-t path

Note dist is not well-defined if there are negative cycles within a graph, because a path can loop
around a negative cycle infinitely to achieve smaller and smaller distances. Hence, we assume
(for now) that graph G has no negative cycles.
Three types of shortest path problems are:

• s-t shortest path: compute dist(s, t).

• Single source shortest path (SSSP): compute dist(s, v) ∀v ∈ V .
• All pairs shortest path (APSP): compute dist(u, v) ∀u, v ∈ V .

Claim. Every subpath of a shortest path is a shortest path.

Proof. Suppose there exists a subpath S = (u, . . . , v) of a shortest path P = (s, . . . , u, . . . , v, . . . , t)

that is not the shortest path from u to v. Let P 0 = (u, . . . , v) be the shortest path from u to v.
Then P can be shortened by replacing S with P 0 , contradicting our assumption that P is a shortest
path.

Given the above claim, we can conclude that the shortest path problem has optimal substructure.

1
Claim. There is always a shortest path with ≤ n − 1 edges.

Proof. Without loss of generality, assume the shortest path between arbitrary s, t, P = (s, . . . , t),
has length n. Since there are n vertices, by the pigeonhole principle some vertex u must appear
twice in the path, so P can be expressed as (s, . . . , u, . . . , u, . . . , t). The subpath u → u in P
contains at least one edge, so if we remove this subpath we obtain a path from s to t with ≤ n − 1
edges.

2 Dynamic Programming for Shortest Path Problems

2.1 The Doubling Path Algorithm for APSP

Given the distance function dist, it may be tempting to write a recursive formulation for dist as
the following:
dist(s, t) = min{dist(s, v) + dist(v, t)}
v∈V
The drawback with this formulation is that it is unclear whether the subproblems are any smaller
than the original problem. To solve this issue, we introduce a new variable: number of edges in the
path.
d(k) (s, t) = min `(P )
P =(s,...,t)
|P |=|{e∈P }|≤k

d(k) (s, t) = min d(bk/2c) (s, v) + d(dk/2e) (v, t)

v∈V

This ensures our subproblems are half the size of the original problem. We can write pseudocode
for this recursive formulation as follows:
for k = 1, . . . .dlog ne:
for all s ∈ V :
for all t ∈ V :
k k−1 k−1
d(2 ) (s, t) = min{d(2 ) (s, v) + d(2 ) (v, t)}
v∈V

To initialize the table, we set up


0
 s=t
(20 )
6 t
d (s, t) = `(s, t) s =

∞ (s, t) ∈
/ E.


The runtime of this algorithm is O(n3 log n). In order from outer to inner, each for loop takes
O(log n), O(n), and O(n) time; and the distance calculation requires iterating over O(n) vertices.

2.2 Toward SSSP

So, this is not bad, but it is pretty wasteful if all you want to solve is single source shortest path.
That is, O(n3 log n) is not necessarily the best you can do, if the only thing in your mind is single

2
source shortest path. The reason that it is wasteful for single source shortest path problem is that
even if s is fixed, you start solving some problems that do not involve s as a source. So we need
to go back to the recurrence formulation and say: how do we express shortest path in a different
recurrence formulation that is more mental to single source shortest path?
A good recursive formulation is going to solve some problems that we already want to solve it
anyway. If we want to solve a single source shortest path going out from s, the all subproblems we
generate or we need to solve anyway should be also shortest distances going out from s.
Hence, we come up with the following recurrence formulation:


0 s=t

∞ s 6= t and k = 0

d(k) (s, t) =

 min {d(k−1) (s, u) + `(u, v)}
 u∈V

s.t. (u,v)∈E

Note k indicates the maximum number of edges we are allowed to use in a path. The pseudocode
is as follows:
For k = 1..n − 1:
For each v ∈ V :
d(k) (s, v) = min {d(k−1) (s, u) + `(u, v)}
u∈V
s.t. (u,v)∈E

This is a O(nm) algorithm. The outer loop is O(n) as it loops through values k = 1..n − 1. Then
for each vertex v ∈ V , we pick an edge e = (u, v) that minimizes the total path length from s to
t that passes through e; we have to check at most deg(v) edges (number of in-degrees of v). Thus
the inner for loop sums the degrees of each vertex in V and this sum is O(m) (the sum of the
in-degrees in a directed graph is m).

2.3 Bellman Ford Algorithm for Single Source Shortest Path

Bellman Ford implements the idea in the above recurrence, but uses the observation that it is not
necessary to explicitly keep track of the number of edges in the path.
(
0 s=v
Initialize d(v) = ∀v ∈ V
∞ s 6= v
Repeat n − 1 times :
For any (u, v) ∈ E :
/* The step below is called " Edge Relaxation " */
d(v) = min{d(v), d(u) + `(u, v)}

Lemma 1 (Correctness Lemma).

1. d(v) = length of some path from s to v, that is, d(v) ≥ dist(s, v).
2. After k iterations of the outer loop, d(v) ≤ d(k) (s, v) ∀v ∈ V .

3
 (
0 s=v
Proof. Let k = 0. Then for any v ∈ V , d(v) = . We can observe this satisfies the
∞ o.w.
conditions d(v) < ∞ when there is a path from s to v, and d(v) ≤ d(0) (s, v).
Suppose for 1 ≤ k < n − 1 we know the above conditions are satisfied. Now, consider d(v) for v ∈ V
after iteration k + 1.
Observe that d(v) can only decrease or stay the same. Further, since every subpath in a shortest
path is a shortest path, the shortest path found in d(k+1) (s, v) must contain a shortest path,
on ≤ k edges, from s to u∗ for some vertex u∗ where edge (u∗ , v) exists. Then it follows that
d(u∗ ) ≤ d(k) (s, u∗ ) =⇒ d(v), after iteration k + 1, satisfies d(v) ≤ d(k+1) (s, v) since using the
subpath from s to u∗ was checked by the algorithm.

Runtime Analysis. The Bellman Ford algorithm runs in O(nm) time as the outer for loop
loops n − 1 times, while the inner loops over the edge set.

2.4 Floyd Warshall Algorithm for All Pairs Shortest Path

Enumerate the vertices V = {v1 , . . . , vn }. Define

d(k) (s, t) = min `(P )

P =(s,intermediate vertices V 0 ,t)
vi ∈V 0 =⇒ i≤k

In English, d(k) (s, t) is the shortest path from s to t using only intermediate vertices numbered
1, . . . , k. This can be expressed recursively as follows:
(
d(k−1) (s, t)
d(k) (s, t) = min (k−1)
d (s, vk ) + d(k−1) (vk , t)

The pseudocode is below:


0
 vi = vj
(0)
Initialize d (vi , vj ) = `(vi , vj ) (vi , vj ) ∈ E

∞

otherwise
for k = 1..n:
for all i = 1..n:
for all j = 1..n:
(
d(k−1) (s, t)
d(k) (vi , vj ) = min (k−1)
d (s, vk ) + d(k−1) (vk , t)

Runtime Analysis. The runtime of the Floyd Warshall algorithm in O(n3 ) as there are three
for loops each with n iterations.