Algorithms

CSE 245

All Pairs of Shortest Path

 All-Pairs Shortest Paths
• Given: 2
3 4
– Directed graph G = (V, E)
8
1 3
– Weight function w : E → R 2
1
-4 7 -5
• Compute:
5 4
6
– The shortest paths between all pairs
of vertices in a graph
– Representation of the result: an
n × n matrix of shortest-path
distances δ(u, v)

2
 Dijkstra (G, w, s)
1. INITIALIZE-SINGLE-SOURCE(V, s) (V)
2. S ← 
3. Q ← V[G] O(V) build min-heap
4. while Q   Executed O(V) times
5. do u ← EXTRACT-MIN(Q) O(lgV)
6. S ← S  {u}
7. for each vertex v  Adj[u]
8. do RELAX(u, v, w) O(E) times; O(lgV)
Running time: O(VlgV + ElgV) = O(ElgV)
3
 BELLMAN-FORD(V, E, w, s)
1. INITIALIZE-SINGLE-SOURCE(V, s) (V)
2. for i ← 1 to |V| - 1 O(V)
3. do for each edge (u, v)  E O(E)
O(VE)

4. do RELAX(u, v, w)
5. for each edge (u, v)  E O(E)
6. do if d[v] > d[u] + w(u, v)
7. then return FALSE
8. return TRUE

Running time: O(VE)

4
All-Pairs Shortest Paths - Solutions
• Run BELLMAN-FORD once from each vertex:
– O(V2E), which is O(V4) if the graph is dense
(E = (V2))
• If no negative-weight edges, could run
Dijkstra’s algorithm once from each vertex:
– O(VElgV) with binary heap, O(V3lgV) if the graph is
dense
• We can solve the problem in O(V3), with no
elaborate data structures
5
 All-Pairs Shortest Paths
• Assume the graph (G) is given as adjacency
matrix of weights
– W = (wij), n x n matrix, |V| = n
– Vertices numbered 1 to n
0 if i = j
wij = weight of (i, j) if i  j , (i, j)  E
∞ if i  j , (i, j)  E
1 1 2 3 4 5
3 v1 v2 1 0 1  1 5
9
5 2 9 0 3 2 
1 2 3 Wait Matrix
v5 3   0 4 
3 2 4   2 0 3
v4 v3
5 3    0
4 6
 All-Pairs Shortest Paths
• Assume the graph (G) is given as adjacency
matrix of weights
– W = (wij), n x n matrix, |V| = n
– Vertices numbered 1 to n
0 if i = j
wij = weight of (i, j) if i  j , (i, j)  E
2
∞ if i  j , (i, j)  E
3 4 1 2 3 4 5
8 1
1 3 2
2 Wait Matrix ?
1 3
-4 7 -5
4
5 4 5
6 7
 All-Pairs Shortest Paths
• Assume the graph (G) is given as adjacency
matrix of weights
– W = (wij), n x n matrix, |V| = n
– Vertices numbered 1 to n
0 if i = j
wij = weight of (i, j) if i  j , (i, j)  E
∞ if i  j , (i, j)  E
• Output the result in an n x n matrix
D = (dij), where dij = δ(i, j)
• Solve the problem using dynamic programming
8
 Optimal Substructure of a Shortest Path
at most m edges
• All subpaths of a shortest

11
j
path are shortest paths i
k
• Let p: a shortest path p
at most m - 1 edges
from vertex i to j that
p’
contains at most m edges • If i  j: p = i kj
– p’ has at most m-1
• If i = j
edges
– w(p) = 0 and p has no – p’ is a shortest path
edges δ(i, j) = δ(i, k) + wkj
9
 Recursive Solution
• lij(m) = weight of shortest path i j that contains
at most m edges
at most m edges
• m = 0: lij(0) = 0 if i = j 
11
j
 i
k
if i  j

• m  1: l (m)
= min { lij
(m-1) , min {l (m-1) + w } }
ik kj
ij 1kn
= min {lik(m-1) + wkj}
1kn

– Shortest path from i to j with at most m – 1 edges

– Shortest path from i to j containing at most m edges,
considering all possible predecessors (k) of j 10
 Computing the Shortest Paths
• m = 1: lij(1) = wij L(1) = W
– The path between i and j is restricted to 1 edge

• Given W = (wij), compute: L(1), L(2), …, L(n-1), where

L(m) = (lij(m))
• L(n-1) contains the actual shortest-path weights
Given L(m-1) and W  compute L(m)
– Extend the shortest paths computed so far by one more edge
• If the graph has no negative cycles: all simple shortest
paths contain at most n - 1 edges
δ(i, j) = l (n-1)
and l = l
(n) (n+1)
... = lij
(n-1)
ij ij ij

11
 Extending the Shortest Path
lij(m) = min {lik(m-1) + wkj}
1kn
k
j j

i * = i
k

L(m-1) nxn W L(m)

Replace: min  + Computing L(m) looks like

+   matrix multiplication

12
 EXTEND(L, W, n)
1. create L’, an n × n matrix
2. for i ← 1 to n
lij(m) = min {lik(m-1) + wkj}
3. do for j ← 1 to n 1kn

4. do lij’ ←∞
5. for k ← 1 to n
6. do lij’ ← min(lij’, lik + wkj)
7. return L’
Running time: (n3)
13
SLOW-ALL-PAIRS-SHORTEST-PATHS(W, n)

1. L(1) ← W

2. for m ← 2 to n - 1
3. do L(m) ←EXTEND (L(m - 1), W, n)

4. return L(n - 1)

Running time: (n4)

14
 Example lij(m) = min {lik(m-1) + wkj}
1kn

2 L(m-1) = L(1) W

3 4 0 3 8  -4 0 3 8  -4
8
1 3  0  1 7  0  1 7
2

-4
1
-5
 4 0    4 0  
7
5 4 2  -5 0  2  -5 0 
6
   6 0    6 0

0 3 8 2 -4 min { D0 [1,4], D0 [1,5]+ D0 [5,4]}

=
3 0 -4 1 7 min {, -4+6} = 2
L(m) = L(2) min { D0 [2,3], D0 [2,4]+ D0 [4,3]}
 4 0 5 11 =
min {, 1+(-5)} = -4
2 -1 -5 0 -2 min { D0 [3,4], D0 [3,2]+ D0 [2,4]}
=
min {, 4+7} = 11
8  1 6 0
15
 Example lij(m) = min {lik(m-1) + wkj}
1kn

L(m-1) = L(2)
2 0 3 8 2 -4
4
3 3 0 -4 1 7
8
1
2
3  4 0 5 11
-4 7
1
-5 2 -1 -5 0 -2
5 4 8  1 6 0
6

0 3 -3 2 -4 min { D1 [2,5], D1 [2,1]+ D1 [1,5]}

=
3 0 -4 1 -1 min {7, 3-4} = -1
L(m) = L(3) min { D1 [3,1], D1 [3,4]+ D1 [4,1]}
7 4 0 5 11 =
min {, 5+2} = 7
2 -1 -5 0 -2 min { D1 [5,2], D1 [5,4]+ D1 [4,2]}
=
min {, 6-1} = 5
8 5 1 6 0
16
 Example lij(m) = min {lik(m-1) + wkj}
1kn

L(m-1) = L(3)
2 0 3 -3 2 -4
4
3 3 0 -4 1 -1
8
1
2
3 7 4 0 5 11
-4 7
1
-5 2 -1 -5 0 -2
5
6
4 8 5 1 6 0

0 1 -3 2 -4 min { D2 [1,2], D2 [1,4]+ D2 [4,2]}

=
3 0 -4 1 -1 min {3, 2-1} = 1
L(m) = L(4) min { D2 [3,5], D2 [3,1]+ D2 [1,5]}
7 4 0 5 3 =
min {11, 7-4} = 3
2 -1 -5 0 -2
8 5 1 6 0
17
 Improving Running Time
• No need to compute all L(m) matrices
• If no negative-weight cycles exist:
L(m) = L(n - 1) for all m  n – 1
• We can compute L(n-1) by computing the sequence:
(Matrix multiplication is associative A*(B*C)=(A*B)*C)
L(1) = W L(2) = W2 = W  W
L(4) = W4 = W2  W2 L(8) = W8 = W4  W4 …
 2x  n 1
 n 1 2  lg( n1) 
L W
18
 FASTER-APSP(W, n)
1. L(1) ← W
2. m←1
3. while m < n - 1
4. do L(2m) ← EXTEND(L(m), L(m), n)
5. m ← 2*m
6. return L(m)

• OK to overshoot: products don’t change after

L(n - 1)
• Running Time: (n3lg n)
19
 The Floyd-Warshall Algorithm
• Given: 2

– Directed, weighted graph G = (V, E) 3 4

8
– Negative-weight edges may be 1
2
3
present -4 7
1
-5
– No negative-weight cycles could be 5 4
6
present in the graph
• Compute:
– The shortest paths between all pairs
of vertices in a graph

20
 The Structure of a Shortest Path
3
• Vertices in G are given by 6
0.5
1 2
V = {1, 2, …, n} 3 4
2 1
• Consider a path p = v1, v2, …, vl 2

5
– An intermediate vertex of p is any

vertex in the set {v2, v3, …, vl-1}

– E.g.: p = 1, 2, 4, 5: {2, 4}

p = 2, 4, 5: {4}

21
 The Structure of a Shortest Path
• For any pair of vertices i, j  V, consider all
paths from i to j whose intermediate vertices
are all drawn from a subset {1, 2, …, k}
– Find p, a minimum-weight path from these paths
p1
pu j
i

pt

No vertex on these paths has index > k

22
 Example
2
4
3
d (0)
45 
8
d (1)
 16
1 3

2
45

14
1 -5
7
5 4

6
 Example
2
4
3
d ( 2)
45  12
1 8 3

2
14
1 -5
7
5 4

6
 Example
2
4
3 d ( 3)
45 6
1 8 3

2
14
1 -5
7
5 4

6
 The Structure of a Shortest Path
• k is not an intermediate vertex of path p
k
– Shortest path from i to j with intermediate
i j
vertices from {1, 2, …, k} is a shortest path
from i to j with intermediate vertices from
{1, 2, …, k - 1}
• k is an intermediate vertex of path p
– p1 is a shortest path from i to k p1 
k p2
j
– p2 is a shortest path from k to j i
– k is not intermediary vertex of p1, p2
– p1 and p2 are shortest paths from i to k with
vertices from {1, 2, …, k - 1}
26
 A Recursive Solution (cont.)
dij(k) = the weight of a shortest path from
vertex i to vertex j with all intermediary
vertices drawn from {1, 2, …, k}

• k=0
• dij(k) = wij

27
 A Recursive Solution (cont.)
dij(k) = the weight of a shortest path from vertex i to
vertex j with all intermediary vertices drawn from
{1, 2, …, k}

• k1
• Case 1: k is not an intermediate
k
vertex of path p i j

• dij(k) = dij(k-1)

28
 A Recursive Solution (cont.)
dij(k) = the weight of a shortest path from vertex i to
vertex j with all intermediary vertices drawn from
{1, 2, …, k}

• k1
• Case 2: k is an intermediate

k
vertex of path p i
j

• dij(k) = dik(k-1) + dkj(k-1)

29
 Computing the Shortest Path Weights

• dij(k) = wij if k = 0
min {dij(k-1) , dik(k-1) + dkj(k-1) }if k  1
• The final solution: D(n) = (dij(n)):
dij(n) = (i, j)  i, j  V
j j

+ (k, j)

i i
(i, k)
D(k-1) D(k)

30
 The Floyd-Warshall algorithm

Floyd-Warshall(W[1..n][1..n])
01 D ¬ W // D(0)
02 for k ¬ 1 to n do // compute D(k)
03 for i ¬1 to n do
04 for j ¬1 to n do
05 if D[i][k] + D[k][j] < D[i][j] then
06 D[i][j] ¬ D[i][k] + D[k][j]
07 return D

Running Time: O(n3)

31
Computing predecessor matrix

 How do we compute the predecessor

matrix? nil if i  j or w  
 ij
 Initialization: p (i, j )  
(0)

i if i  j and wij  
– Updating: p(k)(i,j) = p(k-1)(i,j) if(d(k-1)(i,j)<=d(k-1)(i,k)+(d(k-1)(k,j)
– p(k-1)(k,j) if(d(k-1)(i,j) > d(k-1)(i,k)+(d(k-1)(k,j)
Floyd-Warshall(W[1..n][1..n])
01 …
02 for k ¬ 1 to n do // compute D(k)
03 for i ¬1 to n do
04 for i ¬1 to n do
05 if D[i][k] + D[k][j] < D[i][j] then
06 D[i][j] ¬ D[i][k] + D[k][j]
07 P[i][j] ¬ P[k][j]
08 return D
32
 Example dij(k) = min {dij(k-1) , dik(k-1) + dkj(k-1) }
D(0) = W D(1)
2 1 2 3 4 5 1 2 3 4 5
3 4 1 0 3 8  -4 1 0 3 8  -4
8
1 3 2  0  1 7 2  0  1 7
2

-4
1
-5
3  4 0   3  4 0  
7
5 4 4 2  -5 0  4 2 5 -5 0 -2
6
D(2) 5    6 0 5    6 0
1 2 3 4 5 D(3) D(4)
1 0 3 8 4 -4 0 3 8 4 -4 0 3 -1 4 -4
2  0  1 7  0  1 7 3 0 -4 1 -1
3  4 0 5 11  4 0 5 11 7 4 0 5 3
4 2 5 -5 0 -2 2 -1 -5 0 -2 2 -1 -5 0 -2
5    6 0    6 0 8 5 1 6 0 33
Example dij(k) = min {dij(k-1) , dik(k-1) + dkj(k-1) }
D(5) P(5)
2 1 2 3 4 5 1 2 3 4 5
3 4 1 0 1 -3 2 -4 1 - 3 4 5 1
8
1
2
3 2 3 0 -4 1 -1 2 4 - 4 2 1
-4
1
-5
3 7 4 0 5 3 3 4 3 - 2 1
7
5 4 4 2 -1 -5 0 -2 4 4 3 4 - 1
6
5 8 5 1 6 0 5 4 3 4 5 -

Source: 5, Destination: 1
Shortest path: 8
Path: 5 …1 : 5…4…1: 5->4…1: 5->4->1

Source: 1, Destination: 3
Shortest path: -3
Path: 1 …3 : 1…4…3: 1…5…4…3: 1->5->4->3
 In Class Exercise

2 D (0)  W
4
3 1 2 3 4 5

1 0 3 8 ∞ -4
1 8 3
2 ∞ 0 ∞ 1 7
2 3 ∞ 4 0 ∞ ∞
-4 4 2 ∞ - 0 ∞
1 -5
5 5
7
5 4 ∞ ∞ ∞ 6 0
6
 In Class Exercise

2 D (1)
4
3 1 2 3 4 5

1 0 3 8 ∞ -4
1 8 3
2 ∞ 0 ∞ 1 7
2 3 ∞ 4 0 ∞ ∞
-4 4 2 5 - 0 -2
1 -5
5 5
7
5 4 ∞ ∞ ∞ 6 0
6
 In Class Exercise

2 D ( 2)
4
3 1 2 3 4 5

1 0 3 8 4 -4
1 8 3
2 ∞ 0 ∞ 1 7
2 3 ∞ 4 0 5 11
-4 4
1 -5 2 5 -5 0 -2
5
7 ∞ ∞ ∞ 6 0
5 4

6
 In Class Exercise

2 D ( 3)
4
3 1 2 3 4 5

1 0 3 8 4 -4
1 8 3
2 ∞ 0 ∞ 1 7
2 3 ∞ 4 0 5 11
-4 4
1 -5 2 -1 -5 0 -2
5
7 ∞ ∞ ∞ 6 0
5 4

6
 In Class Exercise

2 D ( 4)
4
3 1 2 3 4 5

1 0 3 -1 4 -4
1 8 3
2 3 0 -4 1 -1
2 3 7 4 0 5 3
-4 4
1 -5 2 -1 -5 0 -2
5
7 8 5 1 6 0
5 4

6
 In Class Exercise

2 D (5)
4
3 1 2 3 4 5

1 0 1 -3 2 -4
1 8 3
2 3 0 -4 1 -1
2 3 7 4 0 5 3
-4 4
1 -5 2 -1 -5 0 -2
5
7 8 5 1 6 0
5 4

6
 PrintPath for Warshall’s Algorithm
PrintPath(s, t)
{
if(P[s][t]==nil){
print(“No path”);
return;
}
else if (P[s][t]==s){
print(s);
}
else{
print_path(s,P[s][t]);
print_path(P[s][t], t);
}
}
Print (t) at the end of the PrintPath(s,t) 41