Algorithms L17.

1
Algorithms
Professor Ashok Subramanian
LECTURE 17
Shortest Paths I
Properties of shortest paths
Dijkstras algorithm
Correctness
Analysis
Breadth-first search
Algorithms L17.2
Paths in graphs
Consider a digraph G = (V, E) with edge-weight
function w : E R. The weight of path p = v
1

v
2
L v
k
is defined to be

=
+
=
1
1
1
) , ( ) (
k
i
i i
v v w p w .
Algorithms L17.3
Paths in graphs
Consider a digraph G = (V, E) with edge-weight
function w : E R. The weight of path p = v
1

v
2
L v
k
is defined to be

=
+
=
1
1
1
) , ( ) (
k
i
i i
v v w p w .
v
1
v
2
v
3
v
4
v
5
4 2 5 1
Example:
w(p) = 2
Algorithms L17.4
Shortest paths
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
o(u, v) = min{w(p) : p is a path from u to v}.
Note: o(u, v) = if no path from u to v exists.
Algorithms L17.5
Optimal substructure
Theorem. A subpath of a shortest path is a
shortest path.
Algorithms L17.6
Optimal substructure
Theorem. A subpath of a shortest path is a
shortest path.
Proof. Cut and paste:
Algorithms L17.7
Optimal substructure
Theorem. A subpath of a shortest path is a
shortest path.
Proof. Cut and paste:
Algorithms L17.8
Triangle inequality
Theorem. For all u, v, x e V, we have
o(u, v) s o(u, x) + o(x, v).
Algorithms L17.9
Triangle inequality
Theorem. For all u, v, x e V, we have
o(u, v) s o(u, x) + o(x, v).
u
Proof.
x
v
o(u, v)
o(u, x) o(x, v)
Algorithms L17.10
Well-definedness of shortest
paths
If a graph G contains a negative-weight cycle,
then some shortest paths may not exist.
Algorithms L17.11
Well-definedness of shortest
paths
If a graph G contains a negative-weight cycle,
then some shortest paths may not exist.
Example:
u v

< 0
Algorithms L17.12
Single-source shortest paths
Problem. From a given source vertex s e V, find
the shortest-path weights o(s, v) for all v e V.
If all edge weights w(u, v) are nonnegative, all
shortest-path weights must exist.
IDEA: Greedy.
1. Maintain a set S of vertices whose shortest-
path distances from s are known.
2. At each step add to S the vertex v e V S
whose distance estimate from s is minimal.
3. Update the distance estimates of vertices
adjacent to v.
Algorithms L17.13
Dijkstras algorithm
d[s] 0
for each v e V {s}
do d[v]
S C
Q V Q is a priority queue maintaining V S
Algorithms L17.14
Dijkstras algorithm
d[s] 0
for each v e V {s}
do d[v]
S C
Q V Q is a priority queue maintaining V S
while Q = C
do u EXTRACT-MIN(Q)
S S {u}
for each v e Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] d[u] + w(u, v)
Algorithms L17.15
Dijkstras algorithm
d[s] 0
for each v e V {s}
do d[v]
S C
Q V Q is a priority queue maintaining V S
while Q = C
do u EXTRACT-MIN(Q)
S S {u}
for each v e Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] d[u] + w(u, v)
relaxation
step
Implicit DECREASE-KEY
Algorithms L17.16
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
Graph with
nonnegative
edge weights:
Algorithms L17.17
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
Initialize:
A B C D E Q:
0
S: {}
0



Algorithms L17.18
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A }
0



A EXTRACT-MIN(Q):
Algorithms L17.19
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A }
0
10
3

10 3
Relax all edges leaving A:

Algorithms L17.20
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A, C }
0
10
3

10 3
C EXTRACT-MIN(Q):

Algorithms L17.21
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A, C }
0
7
3 5
11
10 3
7 11 5
Relax all edges leaving C:

Algorithms L17.22
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A, C, E }
0
7
3 5
11
10 3
7 11 5
E EXTRACT-MIN(Q):

Algorithms L17.23
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A, C, E }
0
7
3 5
11
10 3
7 11 5
7 11
Relax all edges leaving E:
Algorithms L17.24
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A, C, E, B }
0
7
3 5
11
10 3
7 11 5
7 11
B EXTRACT-MIN(Q):
Algorithms L17.25
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A, C, E, B }
0
7
3 5
9
10 3
7 11 5
7 11
Relax all edges leaving B:
9
Algorithms L17.26
Example of Dijkstras
algorithm
A
B D
C E
10
3
1 4 7 9
8
2
2
A B C D E Q:
0
S: { A, C, E, B, D }
0
7
3 5
9
10 3
7 11 5
7 11
9
D EXTRACT-MIN(Q):
Algorithms L17.27
Correctness Part I
Lemma. Initializing d[s] 0 and d[v] for all
v e V {s} establishes d[v] > o(s, v) for all v e V,
and this invariant is maintained over any sequence
of relaxation steps.
Algorithms L17.28
Correctness Part I
Lemma. Initializing d[s] 0 and d[v] for all
v e V {s} establishes d[v] > o(s, v) for all v e V,
and this invariant is maintained over any sequence
of relaxation steps.
Proof. Suppose not. Let v be the first vertex for
which d[v] < o(s, v), and let u be the vertex that
caused d[v] to change: d[v] = d[u] + w(u, v). Then,
d[v] < o(s, v) supposition
s o(s, u) + o(u, v) triangle inequality
s o(s,u) + w(u, v) sh. path s specific path
s d[u] + w(u, v) v is first violation
Contradiction.
Algorithms L17.29
Correctness Part II
Lemma. Let u be vs predecessor on a shortest
path from s to v. Then, if d[u] = o(s, u) and edge
(u, v) is relaxed, we have d[v] = o(s, v) after the
relaxation.
Algorithms L17.30
Correctness Part II
Lemma. Let u be vs predecessor on a shortest
path from s to v. Then, if d[u] = o(s, u) and edge
(u, v) is relaxed, we have d[v] = o(s, v) after the
relaxation.
Proof. Observe that o(s, v) = o(s, u) + w(u, v).
Suppose that d[v] > o(s, v) before the relaxation.
(Otherwise, were done.) Then, the test d[v] >
d[u] + w(u, v) succeeds, because d[v] > o(s, v) =
o(s, u) + w(u, v) = d[u] + w(u, v), and the
algorithm sets d[v] = d[u] + w(u, v) = o(s, v).
Algorithms L17.31
Correctness Part III
Theorem. Dijkstras algorithm terminates with
d[v] = o(s, v) for all v e V.
Algorithms L17.32
Correctness Part III
Theorem. Dijkstras algorithm terminates with
d[v] = o(s, v) for all v e V.
Proof. It suffices to show that d[v] = o(s, v) for every v
e V when v is added to S. Suppose u is the first vertex
added to S for which d[u] > o(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:
s


x
y
u
S, just before
adding u.
Algorithms L17.33
Correctness Part III
(continued)
Since u is the first vertex violating the claimed
invariant, we have d[x] = o(s, x). When x was
added to S, the edge (x, y) was relaxed, which
implies that d[y] = o(s, y) s o(s, u) < d[u]. But,
d[u] s d[y] by our choice of u. Contradiction.
s


x
y
u
S
Algorithms L17.34
Analysis of Dijkstra
while Q = C
do u EXTRACT-MIN(Q)
S S {u}
for each v e Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] d[u] + w(u, v)
Algorithms L17.35
Analysis of Dijkstra
|V |
times
while Q = C
do u EXTRACT-MIN(Q)
S S {u}
for each v e Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] d[u] + w(u, v)
Algorithms L17.36
Analysis of Dijkstra
degree(u)
times
|V |
times
while Q = C
do u EXTRACT-MIN(Q)
S S {u}
for each v e Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] d[u] + w(u, v)
Algorithms L17.37
Analysis of Dijkstra
degree(u)
times
|V |
times
Handshaking Lemma O(E) implicit DECREASE-KEYs.
while Q = C
do u EXTRACT-MIN(Q)
S S {u}
for each v e Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] d[u] + w(u, v)
Algorithms L17.38
Analysis of Dijkstra
degree(u)
times
|V |
times
Handshaking Lemma O(E) implicit DECREASE-KEYs.
Time = O(V T
EXTRACT
-
MIN
+ E T
DECREASE
-
KEY
)
Note: Same formula as in the analysis of Prims
minimum spanning tree algorithm.
while Q = C
do u EXTRACT-MIN(Q)
S S {u}
for each v e Adj[u]
do if d[v] > d[u] + w(u, v)
then d[v] d[u] + w(u, v)
Algorithms L17.39
Analysis of Dijkstra
(continued)
Time = O(V) T
EXTRACT
-
MIN
+ O(E) T
DECREASE
-
KEY
Q T
EXTRACT
-
MIN
T
DECREASE
-
KEY
Total
Algorithms L17.40
Analysis of Dijkstra
(continued)
Time = O(V) T
EXTRACT
-
MIN
+ O(E) T
DECREASE
-
KEY
Q T
EXTRACT
-
MIN
T
DECREASE
-
KEY
Total
array O(V) O(1) O(V
2
)
Algorithms L17.41
Analysis of Dijkstra
(continued)
Time = O(V) T
EXTRACT
-
MIN
+ O(E) T
DECREASE
-
KEY
Q T
EXTRACT
-
MIN
T
DECREASE
-
KEY
Total
array O(V) O(1) O(V
2
)
binary
heap
O(lg V) O(lg V) O(E lg V)
Algorithms L17.42
Analysis of Dijkstra
(continued)
Time = O(V) T
EXTRACT
-
MIN
+ O(E) T
DECREASE
-
KEY
Q T
EXTRACT
-
MIN
T
DECREASE
-
KEY
Total
array O(V) O(1) O(V
2
)
binary
heap
O(lg V) O(lg V) O(E lg V)
Fibonacci
heap
O(lg V)
amortized
O(1)
amortized
O(E + V lg V)
worst case
Algorithms L17.43
Unweighted graphs


Suppose that w(u, v) = 1 for all (u, v) e E.
Can Dijkstras algorithm be improved?
Algorithms L17.44
Unweighted graphs
Use a simple FIFO queue instead of a priority
queue.


Suppose that w(u, v) = 1 for all (u, v) e E.
Can Dijkstras algorithm be improved?
Algorithms L17.45
Unweighted graphs
while Q = C
do u DEQUEUE(Q)
for each v e Adj[u]
do if d[v] =
then d[v] d[u] + 1
ENQUEUE(Q, v)
Use a simple FIFO queue instead of a priority
queue.


Breadth-first search
Suppose that w(u, v) = 1 for all (u, v) e E.
Can Dijkstras algorithm be improved?
Algorithms L17.46
Unweighted graphs
while Q = C
do u DEQUEUE(Q)
for each v e Adj[u]
do if d[v] =
then d[v] d[u] + 1
ENQUEUE(Q, v)
Use a simple FIFO queue instead of a priority
queue.


Analysis: Time = O(V + E).
Breadth-first search
Suppose that w(u, v) = 1 for all (u, v) e E.
Can Dijkstras algorithm be improved?
Algorithms L17.47
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q:
Algorithms L17.48
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a
0
0
Algorithms L17.49
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d
0
1
1
1 1
Algorithms L17.50
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e
0
1
1
2
2
1 2 2
Algorithms L17.51
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e
0
1
1
2
2
2 2
Algorithms L17.52
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e
0
1
1
2
2
2
Algorithms L17.53
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e g i
0
1
1
2
2
3
3
3 3
Algorithms L17.54
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e g i f
0
1
1
2
2
3
3
4
3 4
Algorithms L17.55
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e g i f h
0
1
1
2
2
3
3
4 4
4 4
Algorithms L17.56
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e g i f h
0
1
1
2
2
3
3
4 4
4
Algorithms L17.57
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e g i f h
0
1
1
2
2
3
3
4 4
Algorithms L17.58
Example of breadth-first
search
a
b
c
d
e
g
i
f h
Q: a b d c e g i f h
0
1
1
2
2
3
3
4 4
Algorithms L17.59
Correctness of BFS
Key idea:
The FIFO Q in breadth-first search mimics
the priority queue Q in Dijkstra.
Invariant: v comes after u in Q implies that
d[v] = d[u] or d[v] = d[u] + 1.
while Q = C
do u DEQUEUE(Q)
for each v e Adj[u]
do if d[v] =
then d[v] d[u] + 1
ENQUEUE(Q, v)