Shortest paths
Well-definedness of shortest paths
Well-definedness of shortest paths
LECTURE 22
Consider a digraph G = (V, E) with edge-weight functionw:E→R. Theweightofpathp=v1 → v2 → L → vk is defined to be
Consider a digraph G = (V, E) with edge-weight functionw:E→R. Theweightofpathp=v1 → v2 → L → vk is defined to be
Shortest Paths I
• Properties of shortest paths • Dijkstra’s algorithm
• Correctness
• Analysis
k −1
w(p) = ∑w(vi,vi+1).
k −1
w(p) = ∑w(vi,vi+1).
• Breadth-first search
v 4 –2 v –5 1 v v1 v3 v5 1v3v5
A shortest path from u to v is a path of minimum weight from u to v. The shortest- path weight from u to v is defined as
If a graph G contains a negative-weight cycle, then some shortest paths do not exist.
If a graph G contains a negative-weight cycle, then some shortest paths do not exist.
δ(u, v) = min{w(p) : p is a path from u to v}. Note: δ(u, v) = ∞ if no path from u to v exists.
Example:
…
Optimal substructure
Optimal substructure
Optimal substructure
Theorem. A subpath of a shortest path is a shortest path.
Theorem. A subpath of a shortest path is a shortest path.
Theorem. A subpath of a shortest path is a shortest path.
Paths in graphs
Paths in graphs
Proof. Cut and paste:
Proof. Cut and paste:
i =1
i =1
Example:
v2 v4 24
w(p) = –2
uv
uv
<0
Q ← V
⊳Q is a priority queue maintaining V – S, keyed on d[v]
Q ← V
⊳Q is a priority queue maintaining V – S, keyed on d[v]
Q ← V ⊳Q is a priority queue maintaining V – S,
Graph with nonnegative
Initialize: ∞
B2D B2D B2D
Triangle inequality
Triangle inequality
Single-source shortest paths (nonnegative edge weights)
Theorem. Forallu,v,x∈V,wehave δ(u, v) ≤ δ(u, x) + δ(x, v).
Theorem. Forallu,v,x∈V,wehave δ(u, v) ≤ δ(u, x) + δ(x, v).
Problem. Assume that w(u, v) ≥ 0 for all (u, v) ∈ E. (Hence, all shortest-path weights must exist.) From a given source vertex s ∈ V, find the shortest-path weights δ(s, v) for all v ∈ V.
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
d[s] ← 0
for each v ∈ V – {s}
d[s] ← 0
for each v ∈ V – {s}
d[s] ← 0
for each v ∈ V – {s}
do d[v] ← ∞ S←∅
do d[v] ← ∞ S←∅
do d[v] ← ∞ S←∅
Example of Dijkstra’s algorithm
Example of Dijkstra’s algorithm
Example of Dijkstra’s algorithm
Proof.
IDEA: Greedy.
1. Maintain a set S of vertices whose shortest-
δ(u, v) uv
u
v
while Q ≠ ∅
do u ← EXTRACT-MIN(Q)
while Q ≠ ∅
do u ← EXTRACT-MIN(Q)
δ(u, x)
δ(x, v)
path distances from s are known.
2. Ateachstep,addtoSthevertexv∈V–S
S ← S ∪ {u}
for each v ∈ Adj[u]
S ← S ∪ {u}
for each v ∈ Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
do if d[v] > d[u] + w(u, v)
Implicit DECREASE-KEY
x
whose distance estimate from s is minimum. 3. Update the distance estimates of vertices
x
“A” ← EXTRACT-MIN(Q): ∞ ∞ 10 B D 10 B D 10 B D
edgeweights: A 148 79 0A 148 79 0A 148 79 AAA
3 C E Q:ABCDE3 C E Q:ABCDE3 C E C2E C2E C2E
∞
0∞∞∞∞∞∞0∞∞∞∞∞∞ S: {} S: { A }
adjacent to v.
keyed on d[v]
relaxation then d[v] ← d[u] + w(u, v) step
Example of Dijkstra’s algorithm
Example of Dijkstra’s algorithm
Example of Dijkstra’s algorithm
“C” ← EXTRACT-MIN(Q): 10 ∞
0A 14879 0A 14879 0A 14879
Relax all edges leaving A: 10 ∞
10 B D 10 B D 10 B D
Example of Dijkstra’s algorithm
Example of Dijkstra’s algorithm
Example of Dijkstra’s algorithm
S: { A }
S: { A, C }
Relax all edges leaving C: 7 11 B2D B2D B2D
AAA
Q: A B C D E 3 C E Q: A B C D E 3 C E Q: A B C D E 3 C E
C2E C2E C2E 0∞∞∞∞ 3∞ 0∞∞∞∞ 3∞ 0∞∞∞∞ 35
10 3 ∞ ∞
10 3 ∞ ∞
10 3 ∞ ∞
7 11 5 S: { A, C }
“B” ← EXTRACT-MIN(Q): 7 2 11 10 B D 10 B D 10 B D
“E” ← EXTRACT-MIN(Q): 7 2 11
0A 14879 0A 14879 0A 14879
Relax all edges leaving E: 7 BDBDBD
AAA
Q: A B C D E 3 C E Q: A B C D E 3 C E Q: A B C D E 3 C E C2E C2E C2E
0∞∞∞∞ 35 0∞∞∞∞ 35 0∞∞∞∞ 35
10 3 ∞ ∞
7 11 5 S: { A, C, E }
10 3 ∞ ∞ 7 11 5 7 11
10 3 ∞ ∞
Example of Dijkstra’s algorithm
Example of Dijkstra’s algorithm
Correctness — Part I
Relax all edges leaving B: 10
7 9
“D” ← EXTRACT-MIN(Q): 7 9 B 2 D
Lemma. Initializing d[s] ← 0 and d[v] ← ∞ for all v ∈ V – {s} establishes d[v] ≥ δ(s, v) for all v ∈ V, and this invariant is maintained over any sequence of relaxation steps.
B 2 D B D
10 B D 0A 148 79 0A 148 79
AA
Q: A B C D E 3 C E Q: A B C D E 3 C E C2E C2E
0∞∞∞∞350∞∞∞∞35
10 3 ∞ ∞ 7 11 5 7 11
10 3 ∞ ∞
7 11 5 S: { A, C, E, B, D }
S: { A, C, E, B } 99
7 11
S: { A, C, E }
7 11 5 S: { A, C, E, B } 7 11
2
11
Correctness — Part I
Correctness — Part II
Correctness — Part II
Lemma. Initializing d[s] ← 0 and d[v] ← ∞ for all v∈V–{s}establishesd[v]≥δ(s,v)forallv∈V, and this invariant is maintained over any sequence of relaxation steps.
Lemma. Let u be v’s predecessor on a shortest pathfromstov. Then,ifd[u]=δ(s,u)andedge (u, v) is relaxed, we have d[v] = δ(s, v) after the relaxation.
Lemma. Let u be v’s predecessor on a shortest pathfromstov. Then,ifd[u]=δ(s,u)andedge (u, v) is relaxed, we have d[v] = δ(s, v) after the relaxation.
Proof. Suppose not. Let v be the first vertex for which d[v] < δ(s, v), and let u be the vertex that caused d[v] to change: d[v] = d[u] + w(u, v). Then,
Proof. Observe that δ(s, v) = δ(s, u) + w(u, v). Suppose that d[v] > δ(s, v) before the relaxation. (Otherwise, we’re done.) Then, the test d[v] > d[u] + w(u, v) succeeds, because d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v), and the algorithm sets d[v] = d[u] + w(u, v) = δ(s, v).
d[v] < δ(s, v)
≤ δ(s, u) + δ(u, v)
supposition
triangle inequality
sh. path ≤ specific path v is first violation
≤ δ(s,u) + w(u, v)
≤ d[u] + w(u, v) Contradiction.
Correctness — Part III
Correctness — Part III
Correctness — Part III (continued)
Theorem. Dijkstra’s algorithm terminates with d[v] = δ(s, v) for all v ∈ V.
Theorem. Dijkstra’s algorithm terminates with
d[v]=δ(s,v)forallv∈V. S
u
Analysis of Dijkstra while Q ≠ ∅
Analysis of Dijkstra while Q ≠ ∅
Analysis of Dijkstra while Q ≠ ∅
do u ← EXTRACT-MIN(Q) S ← S ∪ {u}
for each v ∈ Adj[u]
|V | times
do u ← EXTRACT-MIN(Q) S ← S ∪ {u}
for each v ∈ Adj[u]
|V | times
degree(u) times
do u ← EXTRACT-MIN(Q) S ← S ∪ {u}
for each v ∈ Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
Proof. It suffices to show that d[v] = δ(s, v) for every v∈VwhenvisaddedtoS. Supposeuisthefirst vertex added to S for which d[u] > δ(s, u). Let y be the first vertex in V – S along a shortest path from s to u, and let x be its predecessor:
u x
S, just before adding u.
s
x
y
s
u y
u
Since u is the first vertex violating the claimed invariant, we have d[x] = δ(s, x). When x was added to S, the edge (x, y) was relaxed, which implies that d[y] = δ(s, y) ≤ δ(s, u) < d[u]. But, d[u] ≤ d[y] by our choice of u. Contradiction.
s
s x
y
y
|V | times
|V | times
Q
T T
Total
array
O(V2)
array
O(V2) O(E lg V)
array
O(V2) O(E lg V)
Analysis of Dijkstra while Q ≠ ∅
Analysis of Dijkstra while Q ≠ ∅
Analysis of Dijkstra (continued)
degree(u) times
degree(u) times
EXTRACT-MIN DECREASE-KEY
do u ← EXTRACT-MIN(Q) S ← S ∪ {u}
for each v ∈ Adj[u]
do u ← EXTRACT-MIN(Q) S ← S ∪ {u}
for each v ∈ Adj[u]
Time = Θ(V)·T EXTRACT-MIN
+ Θ(E)·T DECREASE-KEY
Unweighted graphs
Unweighted graphs
Unweighted graphs
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
Handshaking Lemma ⇒ Θ(E) implicit DECREASE-KEY’s.
Handshaking Lemma ⇒ Θ(E) implicit DECREASE-KEY’s. Time = Θ(V·TEXTRACT-MIN + E·TDECREASE-KEY)
Analysis of Dijkstra (continued)
Analysis of Dijkstra (continued)
Analysis of Dijkstra (continued)
Time = Θ(V)·TEXTRACT-MIN + Θ(E)·TDECREASE-KEY
Time = Θ(V)·TEXTRACT-MIN + Θ(E)·TDECREASE-KEY
Time = Θ(V)·TEXTRACT-MIN + Θ(E)·TDECREASE-KEY
Q
TEXTRACT-MIN TDECREASE-KEY O(V) O(1)
Total
Q
TEXTRACT-MIN O(V)
TDECREASE-KEY O(1)
Total
Q
TEXTRACT-MIN O(V)
TDECREASE-KEY O(1)
Total
Suppose that w(u, v) = 1 for all (u, v) ∈ E. Can Dijkstra’s algorithm be improved?
Suppose that w(u, v) = 1 for all (u, v) ∈ E.
Can Dijkstra’s algorithm be improved?
• Use a simple FIFO queue instead of a priority
Suppose that w(u, v) = 1 for all (u, v) ∈ E.
Can Dijkstra’s algorithm be improved?
• Use a simple FIFO queue instead of a priority
Note: Same formula as in the analysis of Prim’s minimum spanning tree algorithm.
binary heap
O(lg V)
O(lg V)
binary heap
O(lg V) O(lg V)
O(lg V) O(1)
queue.
queue.
Fibonacci heap
amortized
amortized
O(E + V lg V) worst case
Breadth-first search
while Q ≠ ∅
do u ← DEQUEUE(Q)
for each v ∈ Adj[u] do if d[v] = ∞
then d[v] ← d[u] + 1 ENQUEUE(Q, v)
queue.
d d
Unweighted graphs
Example of breadth-first Example of breadth-first search search
Suppose that w(u, v) = 1 for all (u, v) ∈ E.
Can Dijkstra’s algorithm be improved?
• Use a simple FIFO queue instead of a priority
afh0afh afhafh
Breadth-first search
bg bg
while Q ≠ ∅
do u ← DEQUEUE(Q)
bg bg
Analysis: Time = O(V + E).
Q:
Q: a
for each v ∈ Adj[u] do if d[v] = ∞
ei ei
then d[v] ← d[u] + 1 ENQUEUE(Q, v)
c
c
Example of breadth-first search
Example of breadth-first search
Example of breadth-first search
1bg 1bg 1bg bgbgbg
Q: a b d
Q: a b d c e
Q: a b d c e
dd
ei ei
cc
0afh 0afh 0afh a1fh a1fh a1fh
ddd
ddd
eieiei
eieiei
c 2c2 2c2 ccc
11 122 22
Example of breadth-first search
Example of breadth-first search
Example of breadth-first search
4 0afh 0afh 0afh
a1fh a1fh a1fh ddd
ddd
1bg 1b3g 1b3g bgbgbg
eieiei
eieiei
2c22c232c23 ccc
23334
Q: a b d c e Q: a b d c e g i Q: a b d c e g i f
0
Example of breadth-first Example of breadth-first Example of breadth-first
search
search search
444444 0afh 0afh 0afh
a1fh a1fh a1fh ddd
ddd
1b3g 1b3g 1b3g bgbgbg
eieiei
eieiei
2c23 2c23 2c23 ccc
Q: a b d c e g i f h
Q: a b d c e g i f h
Q: a b d c e g i f h
Example of breadth-first search
Correctness of BFS
44 0afh
while Q ≠ ∅
do u ← DEQUEUE(Q)
a 1 d
f
h
for each v ∈ Adj[u] do if d[v] = ∞
d bg
then d[v] ← d[u] + 1 ENQUEUE(Q,v)
1 b 2c23
c
3
g ei
Key idea:
ei
The FIFO Q in breadth-first search mimics the priority queue Q in Dijkstra.
Q: a b d c e g i f h
• Invariant: v comes after u in Q implies that d[v] = d[u] or d[v] = d[u] + 1.
444