CS2040S

Data Structures and Algorithms

Dynamic Programming…
Puzzle of the Week:

The area of the bottom left

square is 5. What’s the area
of the blue triangle?

Catriona Agg
[Link]
Correction: Prim’s Algorithm
while (![Link]()){
Node v = [Link]();
[Link](v);
for each (Edge e : [Link]()){
Node w = [Link](v);
if () {
[Link](w, [Link]());
[Link](w, v);
}
}
} BUG Assume:
decreaseKey does nothing
if new weight is larger than
old weight
Correction: Prim’s Algorithm
Vertex Weight
B
1 3 A 0

A D

2 10
C

while (![Link]()){
Node v = [Link]();
[Link](v);
for each (Edge e : [Link]()){
Node w = [Link](v);
if () {
[Link](w, [Link]());
[Link](w, v);
}
}
}
Correction: Prim’s Algorithm
Vertex Weight
B
1 3 B 1
C 2
A D

2 10
C

while (![Link]()){
Node v = [Link]();
[Link](v);
for each (Edge e : [Link]()){
Node w = [Link](v);
if () {
[Link](w, [Link]());
[Link](w, v);
}
}
}
Correction: Prim’s Algorithm
Vertex Weight
B
1 3 C 2
D 3
A D

2 10
C

while (![Link]()){
Node v = [Link]();
[Link](v);
for each (Edge e : [Link]()){
Node w = [Link](v);
if () {
[Link](w, [Link]());
[Link](w, v);
}
}
}
Correction: Prim’s Algorithm
Vertex Weight
B
1 3 D 3

A D

2 10
C

while (![Link]()){
Node v = [Link]();
[Link](v);
for each (Edge e : [Link]()){
Node w = [Link](v);
if () {
[Link](w, [Link]());
[Link](w, v);
}
}
}
Correction: Prim’s Algorithm
while (![Link]()){
Node v = [Link]();
[Link](v);
for each (Edge e : [Link]()){
Node w = [Link](v);
if ( && [Link](w)>[Link]()) {
[Link](w, [Link]());
[Link](w, v);
}
}
}
Roadmap
Dynamic Programming
☑ Basics of DP
☑ Example: Longest Increasing Subsequence
– Example: Bounded Prize Collecting
– Example: Vertex Cover on a Tree
– Example: All-Pairs Shortest Paths
Dynamic Programming Basics
Optimal sub-structure:
Optimal solution can be constructed from optimal
solutions to smaller sub-problems.

Big Problem
Solution Merge

Small Small
Problem Small Problem
Problem
Dynamic Programming Basics
Fancy name for:
• Break up a problem into smaller sub-problems
• Optimal solution to sub-problems should be
components of the optimal solution to the
original problem.
• Build the optimal solution iteratively by filling
in a table of sub-solutions
• Take advantage of overlapping sub-problems.
Optimal Sub-structure
Property of (nearly) every problem we study:
– Greedy algorithms
• Dijkstra’s Algorithm
• Minimum Spanning Tree algorithms

– Divide-and-conquer algorithms
• MergeSort
• Fast Fourier Transform
Dynamic Programming
Contrast: Both have optimal substructure

No overlapping subproblems Overlapping subproblems

Divide-and-Conquer Dynamic Programming

Dynamic Programming
Basic strategy: (bottom up dynamic programming)

Step 4: solve root problem

Step 3: combine smaller problems

Step 2: combine smaller problems

Step 1: solve smallest problems

Dynamic Programming
Basic strategy: (DAG + topological sort)

Step 1: Topologically sort DAG

Step 2: Solve problems in reverse order

Dynamic Programming
Basic strategy: (top down dynamic programming)

Step 1: Start at root and recurse.

Step 2: Recurse.

Step 3: Recurse.

Step 4: Solve and memoize.

Only compute each
solution once.
Roadmap
Dynamic Programming
☑ Basics of DP
☑ Example: Longest Increasing Subsequence
– Example: Bounded Prize Collecting
– Example: Vertex Cover on a Tree
– Example: All-Pairs Shortest Paths
Prize Collecting
Input:
– Directed Graph G = (V,E)
– Edge weights w = prizes on each edge

-4
7
-11

-3 2
1
-10 1 -3
-6
3
-5
Prize Collecting
Output:
– Prize collecting path
– Example: 7 + 2 + 1 = 10

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
 What is the maximum prize?

1. 1 -4 7
-11
2. 3 2
-3 1
3. 10 -10 -3
1
-6
4. 15
3
5. 17 -5

6. Infinite

is open
Prize Collecting
Output:
– Prize collecting path: 7 + 2 + 1 - 5 + 3 - 3 - 4 = 1
– Positive weight cycle à infinite prizes!

-4
7
-11

-3 1 2
-10 1 -3
-6
3
-5
Prize Collecting
Check for positive weight cycles using
Bellman-Ford (negating the edges).

-4
7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Input:
– Graph G = (V,E)
– Edge weights w = prizes on each edge
– Limit k: only cross at most k edges

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Note: Not a shortest path problem
– Not a shortest path problem! Longest path…
– Negative weight cycles.
– Positive weight cycles.

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Idea 1:
– Transform G into a DAG
– Make k copies of every node: (v,1), (v,2), (v,3), …
– Solve prize collecting via DAG_SSSP (longest path)

v v
-2 -2 6
-2

w 6 6 z
5 w
5 5
z
k=2 k=1 k=0
Lazy Prize Collecting
Idea 1:
– Transform G into a DAG
– Make k copies of every node: (v,1), (v,2), (v,3), …
– Solve longest-path problem for each source.

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
 What is the running time of Idea 1?

1. O(E)
2. O(VE)
3. O(kE)
4. O(kVE)
5. O(kV2E)
6. None of the above

is open
Lazy Prize Collecting
Running Time:
– Transformed graph: kV nodes, kE edges
– Topo-sort / Longest path: O(kV + kE)
– Once per source: repeat V times è O(kVE)?

-4 7
-11
Whenever you transform
-3 1 2
a graph, do NOT forget
to recompute the number -10 -3
1
of nodes and edges in -6
the new graph.
3
-5
Lazy Prize Collecting
Running Time:
– Transformed graph: kV nodes, kE edges
– Topo-sort / Longest path: O(kV + kE)
– Create super-source….

0
0

0
Lazy Prize Collecting
Idea 2: Dynamic Programming
If you know the optimal solution for (k-1), then it is
easy to computer optimal solution for k.

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Dynamic Programming Recipe
Step 1: Identify optimal substructure
E.g., solution for (k-1) è solution for k

Step 2: Define sub-problems

Step 3: Solve problem using sub-problems

Step 4: Write (pseudo)code.

Lazy Prize Collecting
Dynamic Programming
P[v, k] = maximum prize that you can collect starting
at v and taking exactly k steps.

-4 7
Modified subproblem: -11
Leads to better
optimal substructure. -3 1 2
-10 1 -3
Often, useful to solve -6
modified problem.
3
-5
 P(v, 0) = ?? v
-4 7
-11
1. 0
-3 2
2. 2 1
-10 1 -3
3. -3 -6
4. 4 3
-5
5. 5

is open
Lazy Prize Collecting
Dynamic Programming
P[v, k] = maximum prize that you can collect starting
at v and taking exactly k steps.
P[v, 0] = 0

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Dynamic Programming
P[v, k] = maximum prize that you can collect
starting at v and taking exactly k steps.

Solve P[v,k] using subproblems:

P[v, k] = MAX { P[w1, k-1] + w(v, w1),
P[w2, k-1] + w(v, w2),
P[w3, k-1] + w(v, w3), … }

where [Link]() = {w1, w2, w3, …}

Lazy Prize Collecting
Dynamic Programming
P[v, 1] = max(0+2, 0-3) = 2

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Dynamic Programming
P[v, 1] = max(0+2, 0-3) = 2
P[v, 2] = max(1+2, -5-3) = 3

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Dynamic Programming
P[v, 1] = max(0+2, 0-3) = 2
P[v, 2] = max(1+2, -5-3) = 3
P[v, 3] = max(-4+2, -2-3) = -2

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Dynamic Programming
When is it worth crossing a negative edge?

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
int LazyPrizeCollecting(V, E, kMax) {

int[][] P = new int[[Link]][kMax+1]; // create memo table P

for (int i=0; i<[Link]; i++) // initialize P to zero
for (int j=0; j<kMax+1; j++)
P[i][j] = 0;

for (int k=1; k<kMax+1; k++) { // Solve for every value of k

for (int v = 0; v<[Link]; v++) { // For every node…
int max = -INFTY;
// …find max prize in next step
for (int w : V[v].nbrList()) {
if (P[w,k-1] + E[v,w] > max)
max = P[w,k-1] + E[v,w];
}
P[v, k] = max;
}
}
return maxEntry(P); // returns largest entry in P
}
Lazy Prize Collecting
Dynamic Programming
P[v, k] = maximum prize that you can collect starting
at v and taking exactly k steps.

Total Cost:
Two factors:
– Number of subproblems: kV
– Cost to solve each subproblem: |[Link]|

Total: O(kV2)
Lazy Prize Collecting
Dynamic Programming
P[v, k] = maximum prize that you can collect starting
at v and taking exactly k steps.

Total Cost:
Two factors:
– Number of rows: k
– Cost to solve all problems in a row: E

Total: O(kE)
Roadmap
Dynamic Programming
☑ Basics of DP
☑ Example: Longest Increasing Subsequence
☑ Example: Bounded Prize Collecting
– Example: Vertex Cover on a Tree
– Example: All-Pairs Shortest Paths
Vertex Cover
Input:
Undirected, unweighted graph G = (V,E)
Vertex Cover
Output:
Set of nodes C where every edge is adjacent to at
least one node in C.
Minimum Vertex Cover
NP-complete:
No polynomial time algorithm (unless P=NP).
Easy 2-approximation (via matchings).
Nothing better known.
Vertex Cover on a Tree
Input:
– Undirected, unweighted tree G = (V,E)
– Root of tree r
Vertex Cover on a Tree
Output:
– size of the minimum vertex cover
Dynamic Programming Recipe
Step 1: Identify optimal substructure

Step 2: Define sub-problems

Step 3: Solve problem using sub-problems

Step 4: Write (pseudo)code.

Vertex Cover on a Tree
What are the subproblems?
Vertex Cover on a Tree
S[v, 0] = size of vertex cover in subtree rooted at
node v, if v is NOT covered.
S[v, 1] = size of vertex cover in subtree rooted at
node v, if v IS covered.

v v

S[v, 0] = 2 S[v, 1] = 1
 How many subproblems?

v
1. 2
2. V
3. 2V
4. E
5. 2E
6. VE

is open
Vertex Cover on a Tree
What is the base case?
Vertex Cover on a Tree
What is the base case?
Start at the leaves!

S[leaf, 0] = 0
S[leaf, 1] = 1
Vertex Cover on a Tree
How do we calculate S[v, 0]?
Vertex Cover on a Tree
How do we calculate S[v, 0]?
If we do not cover v, then we need to cover all of v’s children.
Remember: we have already solved the subproblems!

S[v, 0] = S[w1, 1] + S[w2, 1] + S[w3, 1] + …

[Link]() = {w1, w2, w3, … }
Vertex Cover on a Tree
How do we calculate S[v, 1]?
We can either cover or uncover v’s children.

W1 = min(S[w1, 0], S[w1, 1])

W2 = min(S[w2, 0], S[w2, 1])
W3 = min(S[w3, 0], S[w3, 1])

S[v, 1] = 1 + W1 + W2 + W3 + …
[Link]() = {w1, w2, w3, … }
int treeVertexCover(V){//Assume tree is ordered from root-to-leaf

int[][] S = new int[[Link]][2]; // create memo table S

for (int v=[Link]-1; v>=0; v--){//From the leaf to the root

if ([Link]().size()==0) { // If v is a leaf…
S[v][0] = 0;
S[v][1] = 1;
}
else{ // Calculate S from v’s children.
int S[v][0] = 0;
int S[v][1] = 1;
for (int w : V[v].childList()) {
S[v][0] += S[w][1];
S[v][1] += [Link](S[w][0], S[w][1]);
}
}
}
return [Link](S[0][0], S[0][1]); // returns min at root
}
Vertex Cover on a Tree
Running time:
– 2V sub-problems
– O(V) time to solve all sub-problems.
• Each edge explored once.
• Each sub-problem involves exploring children edges.
Roadmap
Dynamic Programming
☑ Basics of DP
☑ Example: Longest Increasing Subsequence
☑ Example: Bounded Prize Collecting
Example: Vertex Cover on a Tree
– Example: All-Pairs Shortest Paths
All Pairs Shortest Path
Input:
– Directed, weighted graph G = (V,E)

Goal:
– Preprocess G
– Answer queries: min-distance(v, w)?

Example:
– On-line map service
All Pairs Shortest Path
Simple solution:
– Run Dijkstra’s Algorithm on every query

Cost:
– Preprocessing: 0
– Responding to q queries: O(q*E*log V)
All Pairs Shortest Path
Simple solution++:
On query(v,w):
• Run Dijkstra’s Algorithm from source v
• Set dist[v,*] = ….
• Next time, on query(v, ?) don’t run Dijkstra’s.

Cost:
– Preprocessing: 0
– Responding to q queries: O(VE*log V)
All Pairs Shortest Path
Preprocessing solution:
On preprocessing:
• For all (v,w): calculate distance(v,w)
On query:
• Return precalculated value.

Cost:
– Preprocessing: all-pairs-shortest-paths
– Responding to q queries: O(q)
Diameter of a Graph
Input:
Undirected, weighted graph G=(V, E)

Output:
A pair of nodes (v,w) such that the shortest path
from v to w is maximal.
Diameter of a Graph
Example:
diameter = 3
Diameter of a Graph
Examples:
In 1999, the diameter of the world-wide-web was
(supposedly) 19.

Milgram claimed in the 1960’s that the diameter of

the United Social social network was 6.
(“Six degrees of separation”)

Diameter of the Erdos collaboration graph is 23.

All Pairs Shortest Paths
Input:
– Weighted, directed graph G = (V,E)

Output:
– dist[v,w] : shortest distance from v to w, for all
pairs of vertices (v,w)
All Pairs Shortest Paths
Input:
– Weighted, directed graph G = (V,E)

Output:
– dist[v,w] : shortest distance from v to w, for all
pairs of vertices (v,w)

Solution:
– Run single-source-shortest paths once for every
vertex v in the graph.
 What is the running time of running SSSP
for every vertex in V on a connected graph
with positive weights (using AVL tree
implementation of priority queues)?

1. O(VE)
2. O(V2E)
3. O(V2 + E2)
4. O(E log V)
5. O(V2log E)
6. O(VE log V)
is open
All Pairs Shortest Paths
Solution:
– Run single-source-shortest paths once for every
vertex v in the graph .
– Assume weights are all positive…
Note:
– In a sparse graph where E = O(V): O(V2log V)
• We don’t know how to do any better.
 What is the running time of running SSSP
for every vertex in V on a connected graph
with all identical weights?

1. O(VE)
2. O(V2E)
3. O(V2 + E2)
4. O(E log V)
5. O(V2log E)
6. O(VE log V)

is open
All Pairs Shortest Paths
Solution:
– Run single-source-shortest paths once for every
vertex v in the graph .
– Assume weights are all positive…
Note:
– In a sparse graph where E = O(V): O(V2log V)
• We don’t know how to do any better.
– Identical weights, use BFS: O(V(E+V)) = O(VE)
• In dense graph: O(V3)
• In sparse graph: O(V2)
Dynamic Programming Recipe
Step 1: Identify optimal substructure

Step 2: Define sub-problems

Step 3: Solve problem using sub-problems

Step 4: Write (pseudo)code.

Floyd-Warshall
Dynamic programming:
Shortest paths have optimal sub-structure:
If P is the shortest path (uàvàw), then P contains the
shortest path from (uàv) and from (vàw).
Floyd-Warshall
Dynamic programming:
Shortest paths have optimal sub-structure:
If P is the shortest path (uàvàw), then P contains the
shortest path from (uàv) and from (vàw).

Shortest paths have overlapping subproblems

Many shortest path calculations depends on the same
sub-pieces.
Floyd-Warshall
Dynamic programming:
Shortest paths have optimal sub-structure:
If P is the shortest path (uàvàw), then P contains the
shortest path from (uàv) and from (vàw).

Shortest paths have overlapping subproblems

Many shortest path calculations depends on the same
sub-pieces.

Hard question: what are the right subproblems?

Floyd-Warshall
Dynamic programming:

Let S[v,w,P] be the shortest path from v to w that

only uses intermediate nodes in the set P.

P
w
v
Floyd-Warshall
Let S[v,w,P] be the shortest path from v to w that
only uses intermediate nodes only in the set P.

P1 = no nodes (empty set)

P2 = green nodes
P3 = purple nodes 40
w
40

100
10
v

10
10
Floyd-Warshall
Let S[v,w,P] be the shortest path from v to w that
only uses intermediate nodes only in the set P.

P1 = no nodes (empty set)

P2 = green nodes
P3 = purple nodes 40
w
40

S(v,w,P1) = 100 100

10
S(v,w,P2) = 80 v

S(v,w,P3) = 30 10
10
Floyd-Warshall
Let S[v,w,P] be the shortest path from v to w that
only uses intermediate nodes only in the set P.

Base case:
S[v, w, Æ] = E[v,w]
40
w
40

100
10
E[v,w] = weight of
v
edge from v to w. 10
10
Floyd-Warshall
Dynamic programming:
Let S[v,w,P] be the shortest path from v to w that
only uses intermediate nodes in the set P.

Problem: 2n possible sets P

è slow to solve all subproblems

P
w
v
Floyd-Warshall
Limit ourselves to n+1 different sets P:

P0 = Æ
P1 = {1}
P2 = {1, 2}
P3 = {1, 2, 3}
P4 = {1, 2, 3, 4}
…
Pn = {1, 2, 3, 4, …, n}
Dynamic Programming Recipe
Step 1: Identify optimal substructure
– Shortest paths are built out of shortest paths.

Step 2: Define sub-problems

– S(u,v,P) = shortest path from u to v using nodes in P.
– Consider only (n+1) sets P of increasing size.

Step 3: Solve problem using sub-problems

Step 4: Write (pseudo)code.

Floyd-Warshall
Use the precalculated subproblems:

Assume we have calculated S[v,w,P7] = 42.

How do we calculate S[v,w,P8]?

P7 = {1,2,3,4,5,6,7}
w

v
Floyd-Warshall
Use the precalculated subproblems:

Assume we have calculated S[v,w,P7] = 42.

How do we calculate S[v,w,P8]?

Two possibilities:
1. Shortest path using nodes P8 includes node 8.
2. Shortest path using nodes P8 does not include
node 8.
Floyd-Warshall
Use the precalculated subproblems:

S[v,w,P8] = min( S[v, w, P7],

S[v, 8, P7] + S[8, w, P7]

P7 = {1,2,3,4,5,6,7}

v w
P7 = {1,2,3,4,5,6,7} P7 = {1,2,3,4,5,6,7}
8
 Example:

1
2 4

1
0 3
1
3 3
1 5

2 4
1
 0 1 2 3 4
Initially: 0 0 2 1 ¥ 3
1 ¥ 0 ¥ 4 ¥
2 ¥ 1 0 ¥ 1
3 1 ¥ 3 0 5
4 ¥ ¥ ¥ ¥ 0
1
2 4
1
0 3
1 3
3
1 5

2 4
1
 0 1 2 3 4
Step: P = {0} 0 0 2 1 ¥ 3
1 ¥ 0 ¥ 4 ¥
2 ¥ 1 0 ¥ 1
3 1 ¥ 3 0 5
4 ¥ ¥ ¥ ¥ 0
1
2 4
1
0 3
1 3
3 0 1 2 3 4
1 5 0 0 2 1 ¥ 3
2 4 1 ¥ 0 ¥ 4 ¥
1 2 ¥ 1 0 ¥ 1
3 1 3 2 0 4
4 ¥ ¥ ¥ ¥ 0
 0 1 2 3 4
Step: P = {0, 1} 0 0 2 1 ¥ 3
1 ¥ 0 ¥ 4 ¥
2 ¥ 1 0 ¥ 1
3 1 3 2 0 4
4 ¥ ¥ ¥ ¥ 0
1
2 4
1
0 3
1 3
3 0 1 2 3 4
1 5 0 0 2 1 6 3
2 4 1 ¥ 0 ¥ 4 ¥
1 2 ¥ 1 0 5 1
3 1 3 2 0 4
4 ¥ ¥ ¥ ¥ 0
 0 1 2 3 4
Step: P = {0, 1, 2} 0 0 2 1 6 3
1 ¥ 0 ¥ 4 ¥
2 ¥ 1 0 5 1
3 1 3 2 0 4
4 ¥ ¥ ¥ ¥ 0
1
2 4
1
0 3
1 3
3 0 1 2 3 4
1 5 0 0 2 1 6 2
2 4 1 ¥ 0 ¥ 4 ¥
1 2 ¥ 1 0 5 1
3 1 3 2 0 3
4 ¥ ¥ ¥ ¥ 0
 0 1 2 3 4
Step: P = {0, 1, 2, 3} 0 0 2 1 6 2
1 ¥ 0 ¥ 4 ¥
2 ¥ 1 0 5 1
3 1 3 2 0 3
4 ¥ ¥ ¥ ¥ 0
1
2 4
1
0 3
1 3
3 0 1 2 3 4
1 5 0 0 2 1 6 2
2 4 1 5 0 6 4 7
1 2 6 1 0 5 1
3 1 3 2 0 3
4 ¥ ¥ ¥ ¥ 0
Done: P = {0, 1, 2, 3, 4}

1
2 4
1
0 3
1 3
3 0 1 2 3 4
1 5 0 0 2 1 6 2
2 4 1 5 0 6 4 7
1 2 6 1 0 5 1
3 1 3 2 0 3
4 ¥ ¥ ¥ ¥ 0
Floyd-Warshall
Use the precalculated subproblems:

S[v,w,P8] = min( S[v, w, P7],

S[v, 8, P7] + S[8, w, P7]

P7 = {1,2,3,4,5,6,7}

v w
P7 = {1,2,3,4,5,6,7} P7 = {1,2,3,4,5,6,7}
8
int[][] APSP(E){ // Adjacency matrix E
int[][][] S = new int[[Link]][[Link]][[Link]];

// Initialize every pair of nodes for k=0

for (int v=0; v<[Link]; v++)
for (int w=0; w<[Link]; w++)
S[0][v][w] = E[v][w];

// For sets P0, P1, P2, P3, …

for (int k=0; k<[Link]; k++)
// For every pair of nodes
for (int v=0; v<[Link]; v++)
for (int w=0; w<[Link]; w++) {
int currD = S[k][v][w];
int toK = S[k][v][k];
int fromK = S[k][k][w];
S[k+1][v][w] = min(currD, toK+fromK);
}
return S;
}
int[][] APSP(E){ // Adjacency matrix E
int[][] S = new int[[Link]][[Link]];//create memo table S

// Initialize every pair of nodes

for (int v=0; v<[Link]; v++)
for (int w=0; w<[Link]; w++)
S[v][w] = E[v][w];

// For sets P0, P1, P2, P3, …

for (int k=0; k<[Link]; k++)
// For every pair of nodes
for (int v=0; v<[Link]; v++)
for (int w=0; w<[Link]; w++) {
int currD = S[v][w];
int toK = S[v][k];
int fromK = S[k][w];
S[v][w] = min(currD, toK+fromK);
}
return S;
}
int[][] APSP(E){ // Adjacency matrix E
int[][] S = new int[[Link]][[Link]];//create memo table S

// Initialize every pair of nodes

for (int v=0; v<[Link]; v++)
for (int w=0; w<[Link]; w++)
S[v][w] = E[v][w];

// For sets P0, P1, P2, P3, …, for every pair (v,w)
for (int k=0; k<[Link]; k++)
for (int v=0; v<[Link]; v++)
for (int w=0; w<[Link]; w++)
S[v][w] = min(S[v][w], S[v][k]+S[k][w]);
return S;
}
 What is the running time of Floyd Warshall?

1. O(VE)
2. O(VE2)
3. O(V2E)
4. O(V3)
5. O(V3 log E)
6. O(V4)

is open
int[][] APSP(E){ // Adjacency matrix E
int[][] S = new int[[Link]][[Link]];//create memo table S

// Initialize every pair of nodes

for (int v=0; v<[Link]; v++)
for (int w=0; w<[Link]; w++)
S[v][w] = E[v][w]

// For sets P0, P1, P2, P3, …, for every pair (v,w)
for (int k=0; k<[Link]; k++)
for (int v=0; v<[Link]; v++)
for (int w=0; w<[Link]; w++)
S[v][w] = min(S[v][w], S[v][k]+S[k][w]);
return S;
}

Not really faster than running Dijkstra

𝑉 times, but simpler to implement and
handles negative weights.
Floyd-Warshall
Dynamic programming:

Let S[v,w,P] be the shortest path from v to w that

only uses intermediate nodes only in the set P.

P
w
v
Dynamic Programming Recipe
Step 1: Identify optimal substructure
– Shortest paths are built out of shortest paths.

Step 2: Define sub-problems

– S(u,v,P) = shortest path from u to v using nodes in P.
– Consider only (n+1) sets P of increasing size.

Step 3: Solve problem using sub-problems

– S(u,v,P7) = min(S[v,w,P7], S[v, 8, P7] + S[8, w, P7]).

Step 4: Write (pseudo)code.

Floyd-Warshall Variants
Path Reconstruction:
– Return the actual path from (v,w).
– Storing all the shortest paths requires
(potentially) n3 space!
(n choose 2) pairs * n hops on the path

– How to represent it succinctly?

– How to store it efficiently?

is open
Floyd-Warshall Variants
Optimal substructure:

v z w
Shortest
First hop path from
on the z to w.
shortest
path

Shortest path from (v è w) is:

(z + shortest path (z è w)).
Floyd-Warshall Variants
Optimal substructure:

v z w
Shortest
First hop path from
on the z to w.
shortest
path

Only store first hop for each destination.

è routing table!
 How much space to store all shortest paths
in a routing table?

1. O(V2)
2. O(VE)
3. O(VE2)
4. O(V2E)
5. O(V3)
6. O(V3 log E)

is open
Floyd-Warshall Variants
Optimal substructure:

v Shortest z w
Shortest
path v to z. path from
Any node
on the z to w.
shortest
path

Store some node z on the shortest path from v to w.

Recursively find shortest path from v è z and z è w.
Floyd-Warshall Variants
Optimal substructure:

v z w
Shortest
First hop path from
on the z to w.
shortest
path

In Floyd-Warshall, store “intermediate node”

whenever you modify/update the matrix entry
for a pair.
Floyd-Warshall Variants
Transitive Closure:
Return a matrix M where:
• M[v,w] = 1 if there exists a path from v to w;
• M[v,w] = 0, otherwise.
Floyd-Warshall Variants
Minimum Bottleneck Edge:
– For (v,w), the bottleneck is the heaviest edge on
a path between v and w.
– Return a matrix B where:
B[v,w] = weight of the minimum bottleneck.
Longest Simple Path
Which of the following is a viable approach for
an algorithm to find the length of the longest
simple path between two vertices 𝑠 and 𝑡 in a
directed graph? Suppose all edge weights 1.

1. Negate weights and run Bellman-Ford

2. Negate weights and run Floyd-Warshall
3. Different DP-based algorithm
4. None of the above.
Longest Simple Path
• No optimal substructure!

• Length of longest path from 𝑠 to 𝑡 is not the

sum of longest path from 𝑠 to 𝑎 and longest
path from 𝑎 to 𝑡, for some intermediate 𝑎!

• Actually, NP-complete!
Roadmap
Dynamic Programming
☑ Basics of DP
☑ Example: Longest Increasing Subsequence
☑ Example: Bounded Prize Collecting
Example: Vertex Cover on a Tree
Example: All-Pairs Shortest Paths