COMP251: Single source shortest paths
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Cormen et al., 2002)
Problem
What is the shortest road to go from one city to another?
Example: Which road should I take to go from Montréal to Boston (MA)?
Variants:
• What is the fastest road?
• What is the cheapest road?
Modeling as graphs • DirectedgraphG=(V,E)
• Weightfunctionw:E➝R Weightofpathp=⟨v0,v1,…,vk ⟩
Input:
n ∑w(vk−1,vk )
=
= sum of edges weights on path p
k=1
Shortest-path weight u to v:
”
$ min w(p):u! v If there exists a path u v.
p δ(u,v)=# { }
$%
Shortest path u to v is any path p such that w(p) = δ(u,v) Generalization of breadth-first search to weighted graphs
∞
Otherwise.
Example
6 3
s
x
t
21427 3
5
y6z
Shortest path from s?
Example
t6x 39
3
s0
5
21427 3
5 11 y6z
Shortest paths are organized as a tree. Vertices store the length of the shortest path from s.
Example
t6x 39
3
s0
5
21427 3
5 11 y6z
Shortest paths are not necessarily unique!
Variants
• Single-source: Find shortest paths from a given source
vertex s ∈ V to every vertex v ∈ V.
• Single-destination: Find shortest paths to a given
destination vertex.
• Single-pair: Find shortest path from u to v.
Note: No way to known that is better in worst case than solving the single-source problem!
• All-pairs: Find shortest path from u to v for all u, v ∈ V .
Negative weight edges Negative weight edges can create issues.
Why? If we have a negative-weight cycle, we can just keep going around it, and get w(s, v) = −∞ for all v on the cycle.
When? If they are reachable from the source (Corollary: It is OK to have a negative-weight cycles if it is not reachable from the source).
What? Some algorithms work only if there are no negative- weight edges in the graph. We must specify when they are allowed and not.
Cycles
Shortest paths cannot contain cycles:
• Negative-weight: Already ruled out.
• Positive-weight: we can get a shorter path by omitting the cycle.
• Zero-weight: no reason to use them ⇒ assume that our solutions will not use them.
Optimal substructure
Lemma
Any subpath of a shortest path is a shortest path.
Proof: (cut and paste) pxy
uxyv
Suppose this path p is a shortest path from u to v. Then δ(u,v) = w(p) = w(pux) + w(pxy) + w(pyv).
Optimal substructure
Lemma
Any subpath of a shortest path is a shortest path.
Proof: (cont’d) uxyv
pxy p’xy
p’xy
Now suppose there exists a shorter path x
Then w(p’xy)
d[v] ß d[u]+w(u,v) π[v]ßu
u3vu3v 4946
Relax
47
46
Triangle inequality
For all (u,v)∈ E, we have δ(u,v) ≤ δ(u,x) + δ(x,v).
Proof:
Weight of shortest path u v is ≤ weight of any path u v. Path u x v is a path u v, and if we use a shortest
path u x and x v, its weight is δ(u, x) + δ (x, v). δ(u,v)
uv δ(u,x)
δ(x, v)
x
Upper bound property
Always have δ(s, v) ≤ d[v] for all v. Once d[v] = δ(s, v), it never changes.
Proof:
• Initially true.
• Then, assume it exists a vertex v such that d[v] < δ(s, v). WLOG, v is the first vertex for which this happens.
Let u be the vertex that causes d[v] to change. Then d[v] = d[u] + δ(u, v). But, we also have:
d[v]<δ(s,v)≤ δ(s,u)+δ(u,v)≤ d[u]+δ(u,v) (triangle inequality) (v is first violation)
⇒d[v] < d[u] + δ(u,v). Contradicts d[v] = d[u] + δ(u, v).
No-path property
If δ(s, v) = ∞, then d[v] = ∞ always.
Proof: d[v] ≥ δ(s,v) = ∞ ⇒ d[v] = ∞.
Convergence property
If:
1. s u➝visashortestpath, 2. d[u] = δ(s,u),
3. we call RELAX(u,v,w),
then d[v] = δ(s,v) afterward.
Proof:
After relaxation: d[v] ≤ d[u] + w(u,v)
= δ(s, u) + w(u, v) = δ(s, v)
(RELAX code)
(d[u] = δ(s,u))
(s u ➝ v is a shortest path
& lemma sub-optimal structure)
Since d[v] ≥ δ(s, v), must have d[v] = δ(s, v).
Path-relaxation property
Let p = ⟨v0,v1,...,vk⟩ be a shortest path from s = v0 to vk. If we relax, in order, (v0,v1), (v1,v2),..., (vk−1,vk), even intermixed with other relaxations, then d[vk] = δ(s,vk).
v0 v1 v2 Vk-1 vk
Proof:
Induction to show that d[vi]=δ(s,vi) after (vi−1,vi) is relaxed. Basis: i = 0. Initially, d[v0] = 0 = δ(s, v0) = δ(s,s).
Inductive step: Assume d[vi−1] = δ(s,vi−1). Relax (vi−1,vi). By convergence property, d[vi] = δ(s, vi) afterward and d[vi] never changes.
Single-source shortest paths in a DAG
DAG ⇒ no negative-weight cycles.
DAG-SHORTEST-PATHS(V,E,w,s)
topologically sort the vertices INIT-SINGLE-SOURCE(V,s)
for each vertex u in topological order do
for each vertex v∈Adj[u] do RELAX(u,v,w)
61
s2t7 -1y-2z
x
4
2
Example
61
s2t7 -1y-2z 0∞∞∞∞
x
4
2
Example
61
s2t7 -1y-2z 026∞∞
x
4
2
Example
61
s2t7 -1y-2z
02664
x
4
2
Example
61
s2t7 -1y-2z
02654
x
4
2
Example
61
s2t7 -1y-2z
02653
x
4
2
Example
61
s2t7 -1y-2z
02653
x
4
2
Single-source shortest paths in a DAG
DAG-SHORTEST-PATHS(V,E,w,s)
topologically sort the vertices INIT-SINGLE-SOURCE(V,s)
for each vertex u in topological order do
for each vertex v ∈ Adj[u] do RELAX(u,v,w)
Time: (V + E).
Correctness:
Because we process vertices in topologically sorted order, edges of any path must be relaxed in order of appearance in the path. ⇒ Edges on any shortest path are relaxed in order.
⇒ By path-relaxation property, correct.
Dijkstra’s algorithm
• No negative-weight edges.
• Weighted version of BFS:
• Instead of a FIFO queue, uses a priority queue.
• Keys are shortest-path weights (d[v]).
• Have two sets of vertices:
• S = vertices whose final shortest-path weights are determined,
• Q=priorityqueue=V−S.
• Similar Prim’s algorithm, but computing d[v], and using shortest-
path weights as keys.
• Greedy choice: At each step we choose the light edge.
Dijkstra’s algorithm
DIJKSTRA(V, E,w,s) INIT-SINGLE-SOURCE(V,s) S←∅
Q←V
whileQ≠ ∅ do
u ← EXTRACT-MIN(Q)
S ← S ∪ {u}
for each vertex v ∈ Adj[u] do
RELAX(u,v,w)
Example
t
10
s0
5
Q
x
2 ∞∞
21427 3
∞∞ y6z
s
t
y
x
z
10
s0
5
Q
2 10
Example
x
∞
t
21427 3
5 y6z
∞
y
t
x
z
Example
t2x 69
10
s0
5
Q
21427 3
5 11 y6z
t
x
z
Example
t2x 68
10
s0
5
Q
21427 3
5 11 y6z
x
z
Example
t2x 68
10
s0
5
Q
21427 3
5 10 y6z
z
Example
t2x 68
10
s0
5
Q
21427 3
5 10 y6z
Example
t2x 68
10
s0
5
21427 3
5 10
y6z
Correctness
Loop invariant:
At the start of each iteration of the while loop, d[v] = δ(s,v) for all v ∈ S.
Initialization:
Initially, S = ∅, so trivially true. Termination:
At end, Q=∅ ⇒ S = V ⇒ d[v] = δ(s,v) for all v ∈ V.
Maintenance:
Show that d[u] = δ(s,u) when u is added to S in each Iteration.
Correctness (cont’d)
Show that d[u] = δ(s,u) when u is added to S in each iteration.
Suppose there exists u such that d[u] ≠ δ(s,u).
Let u be the first vertex for which d[u] ≠ δ(s, u) when u is added to S.
• u≠s,sinced[s]=δ(s,s)=0.
• Therefore,s∈S,soS≠∅.
• There must be some path s u. Otherwise d[u] = δ(s,u) = ∞ by no-path property.
• So,thereisapaths u. Thus,thereisashortestppaths u.
Correctness (cont’d)
Show that d[u] = δ(s,u) when u is added to S in each iteration.
Just before u is added to S, the path p connects a vertex in S (i.e., s) to a vertex in V − S (i.e., u).
Let y be the first vertex along p that is in V − S, and let x ∈ S be y is predecessor.
p2
u xy
Decomposepintos p1 x→y p2 u.
s
p1
S
Correctness (cont’d) Claim 1: d[y] = δ(s, y) when u is added to S.
Proof:
x ∈ S and u is the first vertex such that d[u] ≠ δ(s, u) when u is added to S ⇒ d[x] = δ(s, x) when x is added to S.
But when x is added we relax the edge (x, y), so by the convergence property, d[y] = δ(s, y).
s
p1
S
p2
u xy
Correctness (cont’d)
Show that d[u] = δ(s,u) when u is added to S in each iteration. Now, we can get a contradiction to d[u] ≠ δ(s, u):
y is on shortest path p (s u), and all edge weights are nonnegative. ⇒ δ(s, y) ≤ δ(s, u)
Then by Claim 1, we have d[y] = δ(s,y) ≤ δ(s,u)
≤ d[u] (upper-bound property)
In addition, y and u were in Q when we chose u, thus d[u] ≤ d[y].
We have d[y] ≤ d[u] & d[u] ≤ d[y] ⇒ d[u] = d[y] . Therefore, d[y] = δ(s, y) ≤ δ(s, u) ≤ d[u] = d[y] Contradicts assumption that d[u] ≠ δ(s,u).n
Analysis
Like Prim’s algorithm, it depends on implementation of priority queue.
If binary heap, each operation takes O(lg V ) time ⇒ O(E lg V ).
Note: We can achieve O(V lg V + E) with Fibonacci heaps.