Dynamic programming
Dynamic programming COMP4500/7500
Advanced Algorithms & Data Structures
November 5, 2019
November 5, 2019 1/40
Dynamic programming
Overview this week
November 5, 2019
2/40
Dynamic programming continued: All-pairs shortest paths (n = |V |):
Straightforward approach (⇥(n4))
Straightforward improvement (⇥(n3 lg n)) Floyd-Warshall algorithm (⇥(n3))
Johnson’s algorithm (⇥(n2 lg n) for sparse graphs) (Note: overview only – not dynamic)
“Greedy” algorithms: Characteristics
Comparison to dynamic programming Examples:
Task scheduling Fractional knapsack
Dynamic programming
Overview today
November 5, 2019
3/40
Dynamic programming continued: All-pairs shortest paths (n = |V |):
Straightforward approach (⇥(n4))
Straightforward improvement (⇥(n3 lg n)) Floyd-Warshall algorithm (⇥(n3))
Johnson’s algorithm (⇥(n2 lg n) for sparse graphs) (Note: overview only – not dynamic)
Dynamic programming
Dynamic programming recap
Method for efficiently solving some problems with certain properties:
optimal substructure and
overlapping subproblems.
Process:
Give a (concise & intuitive) recursive definition of the solution;
Transform into a dynamic programming implementation:
Calculate and store solutions to sub-problems in an order that respects sub-problem dependencies.
The key idea:
No solution to a sub-problem is calculated more than once.
Massive speed improvements over a naive recursive implementation are possible:
from exponential-time to polynomial-time!
November 5, 2019
4/40
Dynamic programming
Dynamic programming recap
Examples:
Calculating Fibonacci numbers,
Calculating longest common subsequences of strings. Calculating the fastest order to multiple chains of matrices.
November 5, 2019
5/40
Dynamic programming
Finding all-pairs shortest paths
Problem: Find the shortest path between all pairs of nodes in a graph.
Dijkstra’s finds all shortest paths from one node.
Fastest implementation is O(E + V lg V ), which is O(V 2).
Running Dijkstra’s from all nodes is therefore O(V3). However, this cannot handle negative-weight edges.
Bellman-Ford is O(VE), which is O(V3) already, so with an extra loop for each node gives O(V4).
We can get O(V3) and handle neg-weight edges for all-pairs.
November 5, 2019 6/40
Dynamic programming
Recursive definition of all-pairs
Simplifying assumptions/notation:
There are N vertices with ids conveniently 1, 2, ..N.
Uses an adjacency-matrix representation, with weight(i,j) as the weight of the edge from vertex i to j
If no edge exists, the weight is 1, hence we will always return 1 as the weight of the shortest path if one does not exist.
weight(v, v) = 0 for all v
November 5, 2019
7/40
Dynamic programming
Recursive definition of all-pairs
November 5, 2019
8/40
A path from vertex i to j can be either:
a path with no edges of weight 0, e.g. hii for i = j, a path with more than one edge consisting of:
a path p from vertex i to some vertex k, and the edge (k, j)
The weight of such a path is weight(p) + weight(k, j) Key insight: If the shortest path hi, .., k, ji from i to j has m
edges, then
the path from i to k must have (at most) m 1 edges, and
it must be a shortest path from i to k.
Dynamic programming
Recursive definition of all-pairs
Let shortestPath(i, j)m represent the weight of the shortest path fromi toj ofatmostmedges.
Definition (Shortest path (based on path length))
shortestPath(i, j)0 = ⇢ 0 if i = j shortestPath(i, j)m = 1 otherwise
Hence,
MINk2V (shortestPath(i, k)m 1 + weight(k, j)) shortestPath(i, j)1 = weight(i, j)
Each sub-problem is described by 3 parameters, and so a 3D array required to store solutions.
November 5, 2019 9/40
Dynamic programming
Dynamic implementation of all-pairs
Store shortestPath(i, j)m at L[m, i, j] in a n ⇥ n ⇥ n array L. Calculate L[1], then L[2] from L[1], then L[3] from L[2] etc.
SLOW-APSP(n)
1 2 3 4 5 6 7 8 9
10
T(n) 2 ⇥(n4) November 5, 2019
/ L[m, i, j] is weight of the shortest path from i to j of at most m edges. L = new int[n][n][n] / initialise all elements to 1
L[1] = weights
form=2ton 1
d = L[m 1] d0 = L[m] for i = 1 to n
for j = 1 to n
for k = 1 to n
d0[i, j] = MIN(d0[i, j], d[i, k] + weight(k, j))
10/40
Dynamic programming
Even better
Calculate L[1], then L[2] from L[1],
then L[4] from L[2]), then L[8] (from L[4]) etc.
FASTER-APSP(n)
1 2 3 4 5 6 7 8 9
10 11 12
/ L[m, i, j] is weight of the shortest path from i to j of at most m edges. L = new int[n ⇥ n ⇥ n] / initialise all elements to 1
L[1] = weights
m=1
whilem