COMP251: Dynamic programming (2)
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Kleinberg & Tardos, 2005) & Slides by K. Wayne
SINGLE SOURCE SHORTEST PATHS
Modeling as graphs
Input:
• Directed graph G = (V, E)
• Weight function w : E → R
Weight of path p = ⟨v0,v1,…,vk⟩ n
∑w(vk−1,vk ) k=1
=
= sum of edge weights on path p.
Shortest-path weight u to v:
”
δ(u,v)=$# $%
p min w(p):u!v
If there exists a path u v.
{} ∞
Otherwise.
Shortest path u to v is any path p such that w(p) = δ(u,v).
Generalization of breadth-first search to weighted graphs.
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]).
• Greedy choice: At each step we choose the light edge.
How to deal with negative weight edges?
• Allow re-insertion in queue? ⟹ Exponential running time…
• Add constant to each edge?
043077
6 6 -3 9 6 0
Not working…
Bellman-Ford Algorithm
• Allowsnegative-weightedges.
• Computesd[v]andπ[v]forallv∈V.
• ReturnsTRUEifnonegative-weightcycles reachable from s, FALSE otherwise.
If Bellman-Ford has not converged after V(G) – 1 iterations, then there cannot be a shortest path tree, so there must be a negative weight cycle.
Bellman-Ford Algorithm
• Can have negative-weight edges.
• Will “detect” reachable negative-weight cycles.
Initialize(G, s);
for i := 1 to |V[G]| –1 do
for each (u, v) in E[G] do Relax(u, v, w)
for each (u, v) in E[G] do
if d[v] > d[u] + w(u, v) then
return false return true
Time Complexity is O(VE).
Example
s5x 0 –2 ¥
–4
7
¥
y
Iteration 1
Example
s5x 0 –2 5
–4
7
¥
y
Iteration 1
Example
s5x 0 –2 5
–4
7
-4
y
Iteration 1
Example
s5x 0 –2 5
–4
7
-4
y
Iteration 1
Example
s5x 0 –2 3
–4
7
-4
y
Iteration 2
Example
s5x 0 –2 3
–4
7
-4
y
Iteration 2
Example
s5x 0 –2 3
–4
7
-4
y
Iteration 2
Example
s5x 0 –2 3
–4
7
-4
y
Iteration 2
Example
s5x 0 –2 3
–4
7
-4
y
Example 2
s5x 0 –4 ¥
–4
7
¥
y
Iteration 1
Example 2
s5x 0 –4 5
–4
7
¥
y
Iteration 1
Example 2
s5x 0 –4 5
–4
7
-4
y
Iteration 1
Example 2
s5x 0 –4 5
–4
7
-4
y
Iteration 1
Example 2
s5x 0 –4 3
–4
7
-4
y
Iteration 2
Example 2
s5x 0 –4 3
–4
7
-4
y
Iteration 2
Example 2
s5x 0 –4 3
–4
7
-4
y
Iteration 2
Example 2
s5x -1 –4 3
–4
7
-4
y
Iteration 2
Example 2
s5x -1 –4 3
–4
7
-4
y
Check
Example 2
s5x -1 –4 3
–4
7
d[y] > d[s] + w(s, y) ⟹ FALSE
-4
y
Another Look at Bellman-Ford
Note: This is essentially dynamic programming.
Let d(i, j) = cost of the shortest path from s to i that is at most j hops.
d(i, j) =
0
¥
min({d(k, j–1) + w(k, i): i Î Adj(k)} È {d(i, j–1)})
if i = s Ù j = 0 if i 1 s Ù j = 0
if j > 0
j
i
zuvxy 12345
00¥¥¥¥ 106¥7¥ 206472 302472 4 0 2 4 7 –2
KNAPSACK PROBLEM
Knapsack problem
False start…
New variable
Dynamic programming algorithm
Example
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Max weight W = 11
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example w
M
0
1
2
3
4
5
6
7
8
9
10
11
{}
0
0
0
0
0
0
0
0
0
0
0
0
{1}
0
{1,2}
0
{1,2,3}
0
{1,2,3,4}
0
{1,2,3,4,5}
0
i
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example
M
0
1
2
3
4
5
6
7
8
9
10
11
{}
0
0
0
0
0
0
0
0
0
0
0
0
{1}
0
1
1
1
1
1
1
1
1
1
1
1
{1,2}
0
{1,2,3}
0
{1,2,3,4}
0
{1,2,3,4,5}
0
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example
M
0
1
2
3
4
5
6
7
8
9
10
11
{}
0
0
0
0
0
0
0
0
0
0
0
0
{1}
0
1
1
1
1
1
1
1
1
1
1
1
{1,2}
0
1
{1,2,3}
0
{1,2,3,4}
0
{1,2,3,4,5}
0
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example
M
{1}
{1,2,3}
{1,2,3,4}
{1,2,3,4,5}
0
0
0
0
0
1
1
2
0
1
6
3
0
1
4
0
1
5
0
1
6
0
1
7
0
1
8
0
1
9
0
1
10
0
1
11
{}
0
0
0
1
V +M(i-1,w-w {1,2 } 0
2) 1
M(i-1,w)
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example
M
{}
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
11
{1}
0
1
1
1
1
1
1
1
1
1
0
1
0
1
{1,2}
{1,2,3}
{1,2,3,4}
{1,2,3,4,5}
016
V2+M(i-1,w-w2)
0
0
0
7
M(i-1,w)
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example
M
0
1
2
3
4
5
6
7
8
9
10
11
{}
0
0
0
0
0
0
0
0
0
0
0
0
{1}
0
1
1
1
1
1
1
1
1
1
1
1
{1,2}
0
1
6
7
7
7
7
7
7
7
7
7
{1,2,3}
0
{1,2,3,4}
0
{1,2,3,4,5}
0
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example
M
0
1
2
3
4
5
6
7
8
9
10
11
{}
0
0
0
0
0
0
0
0
0
0
0
0
{1}
0
1
1
1
1
1
1
1
1
1
1
1
{1,2}
0
1
6
7
7
7
7
7
7
7
7
7
{1,2,3}
0
1
6
7
7
18
19
24
25
25
25
25
{1,2,3,4}
0
{1,2,3,4,5}
0
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example
M
0
1
2
3
4
5
6
7
8
9
10
11
{}
0
0
0
0
0
0
0
0
0
0
0
0
{1}
0
1
1
1
1
1
1
1
1
1
1
1
{1,2}
0
1
6
7
7
7
7
7
7
7
7
7
{1,2,3}
0
1
6
7
7
18
19
24
25
25
25
25
{1,2,3,4}
0
1
6
7
7
18
22
24
28
29
29
40
{1,2,3,4,5}
0
i
vi
wi
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
Example
M
{}
{1,2}
{1,2,3}
{1,2,3,4}
{1,2,3,4,5}
0
0
0
0
0
0
1
0
1
1
1
1
2
0
6
6
6
3
0
7
7
7
4
0
5
777
7
7
7
18
18
18
6
19
22
22
7
7
24
28
8
7
Item 4 in solution
24 25 25 25
28
29
9
7
29
34
10
7
29
35
11
{1}
0
1
1
Item 3
67
1
1
in solution
0
1
0
1
0
1
0
1
0
1
0
1
0
1
7
25
40
40
Analysis