Dynamic Programming 3: Shortest Paths Flashcards
Why do we like to have algorithms for directed graphs rather than undirected graphs?
Because we can encode any undirected graph as a directed graph using anti-parallel edges (directed edges from node A to B and node B to A)
What is the major constraint on Djikstra’s algorithm for finding shortest paths?
Edge weights can’t be negative!
What is a negative weight cycle?
A cycle in which the sum of weights is negative.If you take a negative weight cycle from node A back to A repeatedly, you make the distance shorter each time!
What does it mean for the shortest path problem if the graph has a negative weight cycle?
It means the problem is no longer well-defined (you can keep following the NWC and get an ever larger negative distance)
Describe the algorithm for the single source shortest path DP algorithm (Bellman-Ford)
Given directed graph G with source s and assuming no negative weight cycles…
Subproblem:
D(i, z) = length of shortest path from s to z using <= i edges, where 0 <= i <= n-1 and z is a node in G.
Recurrence:
D(0, s) = 0, and D(0, z) = inf for all z != s
D(i, z) = min{D(i-1, z), min{D(i-1, y) + w(y, z)}} (double min!)
Pseudocode: (loosely)
Base cases
Iterate over all i = 1->(n-1)
Iterate over all nodes z
Iterate over all nodes with edges going to z
Then do our min calculations
How do we detect a negative weight cycle when computing single source shortest path DP (Bellman-Ford)?
As we fill out our table (nodes on the x axis and i on the y axis), we will eventually get a row where the values decrease, i.e., D(n, z) < D(n-1, z)
Describe the (good) algorithm for the all-pairs shortest path DP algorithm (Floyd-Warshall)
Given directed graph G with edge weights w(e) and assuming no negative weight cycles…
Subproblem:
Condition on a prefix of intermediate vertices. Let v_1, …, v_n be vertices.
for 0 <= i <= n and 1 <= s, t <= n, let d(i, s, t) be the shortest distance from s to t using only vertices v_1, …, v_i as intermediate vertices.
Recurrence:
D(0, s, t) = w(st) if there is an edge from s to t, inf otherwise
For i >= 1, D(i, s, t) = min(D(i-1, s, t), D(i-1, s, i) + D(i-1, i, t))
Pseudocode: (loosely)
For all pairs s and t, if st exists then D(0, s, t) = w(st), otherwise inf
for all i in 1->n, for all s in 1->n, and for all t in 1->n, D(i, s, t) = min(D(i-1, s, t), D(i-1, s, i) + D(i-1, i, t))
return D(n, s, t)
Why is the O(n^3) Floyd-Warshall algorithm for all-pairs shortest paths better than the O(n^2m) naive reapplication of Bellman-Ford to all-pairs?
Because m, the number of total edges in the graph, can be as large as n^2, so O(n^2m) could be as bad as O(n^4).
What is the difference between the basic DP idea of Bellman-Ford (single-source shortest path) and Floyd-Warshall (all-pairs)?
The input to the subproblem in Bellman-Ford is a prefix of the number of edges, while the input for the Floyd-Warshall subproblem is a prefix of the number of nodes/vertices.
How do we detect a negative weight cycle when computing all-pairs shortest path DP (Floyd-Warshall)?
Check if any diagonal entry in our table is negative! i.e., D(n, y, y) < 0 for some y in V.
