Shortest Paths
Nishant Mehta Lectures 5 and 6
Finding the Fastest Way to Travel between Two Intersections in Vancouver
Granville St
and 4 3 4
Homer St and
W Hastings St
W Hastings St
2 2
6
2 1
5
1
32 251
1
32 45
2 11
2
1
Granville St and
W Pender St
Homer St 1 and
W Pender St
•
•
travel times between cities
(might account for speed limits, traffic, etc.)
Shortest Paths in Weighted Graphs
•
distances
Find fastest way to travel across the country using directed graph representing roads, with edge weights representing:
•
Flight distances between airports.
•
Find a fastest way using flights
•
Might also allow for warps in space-time continuum. Negative travel time
Single-Source Shortest Paths
•
More on this soon
If graph is unweighted: Breadth-First Search is a solution
•
If graph is weighted
•
Every edge is associated with a number: integers,
•
rational numbers, real numbers (might be negative!)
•
An edge weight can represent: Distance, connection cost, affinity
•
•
Input: A weighted directed graph G = (V, E) Input: and a source vertex s
Single-Source Shortest Paths Problem
Output: All single-source shortest paths for s in G, i.e., for all other vertices v in G, a shortest path from s to v.
Apathp=(v0,v1,…,vk)froms=v0 tov=vk •P
is shortest if its length w(p) = kj=1 w(vj 1, vj ) is the minimum possible among all s–v paths
Dijkstra’s Algorithm
Dijkstra’s Algorithm
Input: A simple directed graph G with nonnegative edge-weights and a source vertex s in G
Output: A number d[u] for each vertex u in G such that d[u] is the weight of the shortest path in G from s to u
Dijkstra’s Algorithm – Conceptual Version
Dijkstra(V,E,s): S = {s}
d[s] = 0 While S 6= V
For all v2/ S such that there is an edge (u,v) for some u2 S: Set cost c[v] = min{(u,v): u in S} d[u] + w(u,v)
Of these vertices, let v be one for which c[v] is minimum Add v to S
Set d[v] = c[v]
Dijkstras algorithm: a greedy algorithm
1
1
3
2
9
2
3 7
53
4 11
Dijkstras algorithm: Initializing
+∞ 3
+∞ 1
1
+∞
53
11
0
+∞ 2
9
4
+∞
2 7
+∞
+∞
3
+∞
+∞
Dijkstras algorithm: Initializing Cloud C (consisting of solved subgraph)
+∞ 1
1
+∞
53
11
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
0
2 7
+∞
+∞
Dijkstras algorithm: pull v into C
+∞ 1
1
+∞
53
11
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
0
2 7
+∞
+∞
Dijkstras algorithm: update Cs neighborhood
1
1
1
+∞
53
11
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
0
2 7
4
3
Dijkstras algorithm: pick closest vertex u outside C
1
1
1
+∞
53
11
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
0
2 7
4
3
Dijkstras algorithm: pull u into C
1
1
1
+∞
53
11
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞ relax
3
0
2 7
4
Dijkstras algorithm: update Cs neighborhood
1
1
1
2
3
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
53
0
11
2 7
3
Dijkstras algorithm: pick closest vertex u outside C
1
1
1
2
3
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
53
0
11
2 7
3
Dijkstras algorithm: pull u into C
1
1
1
2
3
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
53
0
11
2 7
3
Dijkstras algorithm: update Cs neighborhood
1
1
1
2
3
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
53
0
11
2 7
3
Dijkstras algorithm: pick closest vertex u outside C
1
1
1
2
3
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
53
0
11
2 7
3
Dijkstras algorithm: pull u into C
1
1
1
2
3
+∞ 2
9
4
+∞
+∞ 3
+∞
3
+∞
53
0
11
2 7
3
Dijkstras algorithm: update Cs neighborhood
5
3
2
9
4
+∞
+∞
3
10
1
1
1
2
3
12
53
0
11
2 7
3
Dijkstras algorithm: pick closest vertex u outside C
5
3
2
9
4
+∞
+∞
3
10
1
1
1
2
3
12
53
0
11
2 7
3
Dijkstras algorithm: pull u into C
1
1
1
2
3
12
5
3
2
9
4
14
+∞
3
10
53
0
11
2 7
3
Dijkstras algorithm: update Cs neighborhood
1
1
1
2
3
12
5
3
2
9
4
14
+∞
3
10
53
0
11
2 7
3
Dijkstras algorithm: pick closest vertex u outside C
1
1
1
2
3
12
5
3
2
9
4
14
+∞
3
10
53
0
11
2 7
3
Dijkstras algorithm: pull u into C
5
3
2
9
14
+∞
3
10
1
1
1
2
3
12
relax
2 7
3
53
0
11
4
Dijkstras algorithm: update Cs neighborhood
5
3
2
9
4
14
+∞
3
10
1
1
1
2
3
8
53
0
11
2 7
3
Dijkstras algorithm: pick closest vertex u outside C
5
3
2
9
4
14
+∞
3
10
1
1
1
2
3
8
53
0
11
2 7
3
Dijkstras algorithm: pull u into C
5
3
2
9
4
14
+∞
3
10
1
1
1
2
3
8
53
0
11
2 7
3
Dijkstras algorithm: update Cs neighborhood
5
3
2
9
4
14
+∞
3
10
1
1
1
2
3
8
53
0
11
2 7
3
Dijkstras algorithm: pick closest vertex u outside C
5
3
2
9
4
14
+∞
3
10
1
1
1
2
3
8
53
0
11
2 7
3
Dijkstras algorithm: pull u into C
5
3
2
9
4
14
+∞
3
10
1
1
1
2
3
8
53
0
11
2 7
3
Dijkstras algorithm: update Cs neighborhood
5
3
2
9
4
14
13
3
10
1
1
1
2
3
8
53
0
11
2 7
3
Dijkstras algorithm: pick closest vertex u outside C
5
3
2
9
4
14
13
3
10
1
1
1
2
3
8
53
0
11
2 7
3
Dijkstras algorithm: pull u into C
1
1
1
2
3
8
5
3
2
9
4
14
13
3
10
53
0
11
2 7
3
Dijkstras algorithm: update Cs neighborhood
1
1
1
2
3
8
5
3
2
9
4
14
13
3
10
53
0
11
2 7
3
Dijkstras algorithm: pick closest vertex u outside C
1
1
1
2
3
8
5
3
2
9
4
14
13
3
10
53
0
11
2 7
3
Dijkstras algorithm: pull u into C
1
1
1
2
3
8
5
3
2
9
4
14
13
3
10
53
0
11
2 7
3
Dijkstra’s Algorithm – Conceptual Version
Dijkstra(V,E,s): S = {s}
d[s] = 0 While S 6= V
For all v2/ S such that there is an edge (u,v) for some u2 S: Set cost c[v] = min{(u,v): u in S} d[u] + w(u,v)
Of these vertices, let v be one for which c[v] is minimum Add v to S
Set d[v] = c[v]
Dijkstra’s Algorithm
Dijkstra(V,E,s): For v in V
d[v] = 1; ⇡[v] = null; d[s] = 0
S= ;
Q = BuildPriorityQueue(V, d) While Q not empty
u = DeleteMin(Q) S = S [u
For v in Adj[u]
Relax(u,v)
RELAX(u,v)
If d[u] + w(u,v) < d[v]
d[v] = d[u] + w(u,v) ⇡[v] = u
Dijkstra(V,E,s): For v in V
d[v] = 1; ⇡[v] = null; d[s] = 0
S= ;
Q = BuildPriorityQueue(V, d) While Q not empty
u = DeleteMin(Q) S = S [u
For v in Adj[u]
If d[u] + w(u,v) < d[v] d[v] = d[u] + w(u,v) ⇡[v] = u UpdatePQ(v, d[v])
For v in V
d[v] = 1; ⇡[v] = null;
d[s] = 0
S = ;
Q = BuildPriorityQueue(V, d) While Q not empty
u = DeleteMin(Q) S = S [u
For v in Adj[u]
If w(u,v) < d[v]
d[v] = w(u,v)
⇡[v] = u UpdatePQ(v, d[v])
Dijkstra vs Prim Prim(V,E,s):
n calls
O(n) for binary or Fibonacci heap
O(log n)/call for binary or Fibonacci heaps
Dijkstra’s Algorithm - Runtime Dijkstra(V,E,s):
For v in V
d[v] = 1; ⇡[v] = null;
d[s] = 0
S= ;
Q = BuildPriorityQueue(V, d) While Q not empty
u = DeleteMin(Q) S = S [u
For v in Adj[u]
at most m calls
If d[u] + w(u,v) < d[v] d[v] = d[u] + w(u,v) ⇡[v] = u UpdatePQ(v, d[v])
O(log n)/call for binary heap O(1)/call for Fibonacci heap
RELAX preserves upper bound property of d[v]
•
• •
Upper bound property: Any sequence of calls to RELAX maintains the invariant that d[v] (s, v) for all v 2 V
Proof: simple exercise Important consequence:
If no path from s to v, then d[v] = 1 always!
•
• • • •
• •
Dijkstra’s Algorithm - Correctness
Claim: for all v in S, the algorithm’s path Pv from s-v is a shortest s-v path
Proof by induction
Base case: |S| = 1, with S = {s}
Clearly, Ps = (s) is a shortest s-s path (of length zero!) Inductive step
Suppose the claim holds for |S| = k Prove that it holds for |S| = k + 1
•
•
• •
Let |S| = k and suppose algorithm is about to add v to S, by way of u in S
Dijkstra’s Algorithm - Correctness
Let Pv be the algorithm’s s-v path after the addition, with penultimate vertex u in S
Consider an arbitrary alternative path Pv0
Pv0 has a first edge (x,y) that crosses the cut (S, V \ S)
w ( P v0 ) ( s , x ) + w ( x , y ) = d [x ] + w (x , y ) d[u] + w(u, v)
= (s, u) + w(u, v)
S
s
xy
v
u
•
Consider an arbitrary alternative path Pv0
Pv0 has a first edge (x,y) that crosses the cut (S, V \ S)
Dijkstra’s Algorithm - Correctness
•
S
s
xy
v
u
Path Pv0 cannot be shorter than Pv
w ( P v0 ) ( s , x ) + w ( x , y ) = d [x ] + w (x , y ) d[u] + w(u, v)
= (s, u) + w(u, v) = w (Pv )
(inductive hypothesis)
(v is next vertex added to S) (inductive hypothesis)
Dijkstra’s Algorithm - Negative Weights
v -2 u
2
s
What would Dijkstra do?
1
“Greed is good.” -Gordon Gekko
“Greed is good.” -Gordon Gekko
``Greed is not good (when a graph has negative edge weights).’'
- Bernie Sanders
Bellman-Ford Algorithm
•
Recall: Path Relaxation Property
• • •
• •
all times thereafter, we have d[vk] = (s,vk) (Proved last time)
Let p = (v0, v1,... vk) be a shortest path from v0 to vk Initialize d and ⇡ with source s
Suppose that a sequence of Relax calls occurs which includes the subsequence:
RELAX(v0, v1), RELAX(v1, v2), ..., RELAX(vk-1, vk)
Then after the last Relax call in this subsequence and for
Bellman-Ford Algorithm
•
Suppose shortest path from vertex s to vertex t
An Observation:
•
consists of 1 edge: p = (v0, v1) with s = v0 and t = v1
•
Then after calling RELAX(v0, v1):
d(t) = d(v1) = (v0, v1) = (s, t)
• •
Shortest path from s to t has been found! How to ensure RELAX(v0, v1) gets called?
Initialize d and ⇡ with source s For each edge (u,v) 2 E
RELAX(u,v)
•
•
How to ensure RELAX(v0, v1), RELAX(v1, v2) gets called?
Initialize d and ⇡ with source s For j = 1 2
For each edge (u,v) 2 E RELAX(u,v)
Bellman-Ford Algorithm
•
Suppose shortest path from vertex s to vertex t
An Observation:
•
consists of 2 edges: p = (s = v0, v1, v2 = t)
•
Then after calling RELAX(v0, v1), RELAX(v1, v2):
d(t) = d(v2) = (v0, v2) = (s, t)
Shortest path from s to t has been found!
Bellman-Ford Algorithm
If no negative cycles, shortest path from vertex s to vertex t consists of (at most) n-1 edges: p = (v0, v1, ..., vk) with k n-1
After calling RELAX(v0, v1), RELAX(v1, v2), ..., RELAX(vk-1, vk):
d(t) = d(vk) = (v0,vk) = (s,t)
•
•
• •
Shortest path from s to t has been found!
How to ensure subsequence RELAX(v0, v1), ..., RELAX(vk-1, vk) of calls occurs?
Initialize d and ⇡ with source s For j = 1 n-1
For each edge (u,v) 2 E RELAX(u,v)
Bellman-Ford Algorithm
BELLMAN-FORD(G, w, s)
Initialize d and ⇡ with source s For j = 1 n-1
For each edge (u,v) 2 E RELAX(u,v)
For each edge (u,v) 2 E If d[v] > d[u] + w(u,v)
Return False Return True
RELAX(u,v)
If d[u] + w(u,v) < d[v]
d[v] = d[u] + w(u,v) ⇡[v] = u
Bellman-Ford Algorithm - Correctness
Claim 1:
If there are no negative cycles:
(A) The algorithm correctly finds the shortest paths
(d[v] = (s,v) for all v) and predecessor array is correct. (B) The algorithm returns True.
Claim 2:
If there is a negative cycle, the algorithm detects it and returns False
Bellman-Ford Algorithm - Correctness
Claim 1:
If there are no negative cycles:
(A) The algorithm correctly finds the shortest paths
(d[v] = (s,v) for all v) and predecessor array is correct.
Proof:
This we already showed in the derivation of the algorithm!
The desired subsequence of calls to RELAX occurs, which is all that is required.
Bellman-Ford Algorithm - Correctness
Claim 1:
If there are no negative cycles: (B) The algorithm returns True
Proof:
We only need to verify that
d[v] d[u] + w(u, v) for all edges (u, v) 2 E
From Claim 1 (A), this is equivalent to
(s, v) (s, u) + w(u, v) for all edges (u, v) 2 E
This must be the case. Why? An s-v path that first visits u and then follows edge (u,v) cannot have less weight than the shortest s-v path
Bellman-Ford Algorithm - Correctness
Claim 2:
If there is a negative cycle, the algorithm detects it and returns False
Proof:
Suppose (for a contradiction) that the algorithm returns True Then d[v] d[u] + w(u, v) for all edges (u, v) 2 E (★)
Let the negative cycle be (v0,v1,...,vk), where v0 = vk Summing inequality (★) over each edge in the cycle yields:
Xk j=1
d [vj ]
Xk j=1
(d [vj 1 ] + w (vj 1 , vj ))
Bellman-Ford Algorithm - Correctness
(Proof of Claim 2)
Suppose (for a contradiction) that the algorithm returns True Then d[v] d[u] + w(u, v) for all edges (u, v) 2 E (★)
Let the negative cycle be (v0,v1,...,vk), where v0 = vk Summing inequality (★) over each edge in the cycle yields:
Xk j=1
Xk j=1
d [vj ]
But since v0 = vk , it holds that
The above implies that 0 Pkj=1 w(vj 1, vj ) , a contradiction of the cycle being negative!
(d [vj 1 ] + w (vj 1 , vj ))
Xk j=1
d[vj] =
Xk j=1
d[vj 1]
Bellman-Ford Algorithm - Time Complexity
•
(For loop from 1 to n-1) * (Nested for loop over edges)
O(n m)
•
Compare to Dijkstra’s algorithm
•
O(m log n)
• •
Dealing with negative-weight edges has a cost!
Single-Source Shortest Paths Algorithms
Type of Graph
Algorithm
Time complexity
Unweighted graph
BFS
O(n + m)
Weighted DAG
Topological sort/DFS-based
O(n + m)
Weighted directed graph (nonnegative weights)
Dijkstra’s - Binary heap
O(m log n)
Dijkstra’s - Fibonacci heap
O(n log n + m)
Weighted directed graph (any weights)
Bellman-Ford
O(n m)
• •
Input: A weighted directed graph G = (V, E)
Output: All shortest paths in G, i.e., for all pairs of Output: vertices s, t in V, a shortest path from s to t
All-Pairs Shortest Paths Problem
•
First approach - run single-source shortest paths algorithm n times, once per choice of source vertex
All-Pairs Shortest Paths
Type of Graph
Algorithm
Time complexity
Dense Graph Time complexity
Nonnegative weights
Dijkstra’s - Binary heap
O(n m log n)
O(n3 log n)
Dijkstra’s - Fibonacci heap
O(n2 log n + m n)
O(n3)
Any weights
Bellman-Ford
O(n2 m)
O(n4)
• •
• •
•
All-Pairs Shortest Paths
Need to store upper bound on shortest paths for every pair of vertices
Switch from array d to matrix D of size n ⇥ n
Dij = upper bound on shortest path from i to j
Switch from predecessor array ⇡ to predecessor matrix ⇧
⇧ij
= predecessor of j in some shortest path from source i
Floyd-Warshall Algorithm
Floyd-Warshall Algorithm
• • •
Let p be a shortest path from i to j.
Clearly, all intermediate vertices in path p are in {1, ..., n}
Also, we can break down p into at most 2 paths whose intermediate vertices are in {1, ..., n-1}
p
ij
all intermediate vertices in {1, ..., n}
Case 1
p
Case 2
n
ij
all intermediate vertices in {1, ..., n-1}
p1
p2
j
i
all intermediate vertices in {1, ..., n-1}
All-Pairs Shortest Paths
For k = 0, 1, ..., n: Let D(k) be the weight of the shortest path ij
•
from i to j for which all intermediate vertices are in {1, ..., k}
p
ij
all intermediate vertices in {1, ..., k}
Case 1
p
ij
all intermediate vertices in {1, ..., k-1}
D(k) = D(k 1) ij ij
Case 2
k
i
all intermediate vertices in {1, ..., k-1}
p1
p2
j
D(k) = D(k 1) + D(k 1) ij ik kj
•
Recurrence: D(k) = min nD(k 1), D(k 1) + D(k 1)o ij ij ik kj
Floyd-Warshall Algorithm
Base case: D(0) = w(i,j) ij
•
Why? Because no intermediate vertices can be used
•
FLOYD-WARSHALL(W )
D(0) = W
For k = 1 n
For i = 1 For j = 1
n
n
Return D(n)
D(k) = min nD(k 1), D(k 1) + D(k 1)o ij ij ik kj
Time Complexity
O(n3)
For k = 1 n For i = 1
n
Floyd-Warshall Algorithm
FLOYD-WARSHALL(W ) D(0) = W
For j = 1
D(k) = min nD(k 1), D(k 1) + D(k 1)o
ij ij ik kj Return D(n)
Correctness? D(n) is weight of shortest path with intermediate ij
vertices in {1, ..., n}. This is shortest path itself!
n
Floyd-Warshall Algorithm
What about that predecessor matrix? How do we print a shortest path?
Case 1: D(k 1) + D(k 1) D(k 1) ik kj ij
Path will not change
Reuse predecessor from before: ⇧(k) = ⇧(k 1)
Case 2: D(k 1) + D(k 1) < D(k 1) ik kj ij
Path updates to (path from i to k) (path from k to j)
⇧(k) = ⇧(k 1) ij kj
“Set predecessor of j in shortest path from source i using intermediate vertices in {1, ..., k}
to be predecessor of j in shortest path from source k using intermediate vertices in {1, ..., k-1}”
ij ij