Shortest Path Algorithms
Jaehyun Park
CS 97SI
Stanford University
June 29, 2015
Shortest Path Problem
◮ Input: a weighted graph G = (V, E)
– The edges can be directed or not
– Sometimes, we allow negative edge weights
– Note: use BFS for unweighted graphs
◮ Output: the path between two given nodes u and v that
minimizes the total weight (or cost, length)
– Sometimes, we want to compute all-pair shortest paths
– Sometimes, we want to compute shortest paths from u to all
other nodes
2
Outline
Floyd-Warshall Algorithm
Dijkstra’s Algorithm
Bellman-Ford Algorithm
Floyd-Warshall Algorithm 3
Floyd-Warshall Algorithm
◮ Given a directed weighted graph G
◮ Outputs a matrix D where dij is the shortest distance from
node i to j
◮ Can detect a negative-weight cycle
◮ Runs in Θ(n3 ) time
◮ Extremely easy to code
– Coding time less than a few minutes
Floyd-Warshall Algorithm 4
Floyd-Warshall Pseudocode
◮ Initialize D as the given cost matrix
◮ For k = 1, . . . , n:
– For all i and j:
◮ dij := min(dij , dik + dkj )
◮ If dij + dji < 0 for some i and j, then the graph has a
negative weight cycle
◮ Done!
– But how does this work?
Floyd-Warshall Algorithm 5
How Does Floyd-Warshall Work?
◮ Define f (i, j, k) as the shortest distance from i to j, using
nodes 1, . . . , k as intermediate nodes
– f (i, j, n) is the shortest distance from i to j
– f (i, j, 0) = cost(i, j)
◮ The optimal path for f (i, j, k) may or may not have k as an
intermediate node
– If it does, f (i, j, k) = f (i, k, k − 1) + f (k, j, k − 1)
– Otherwise, f (i, j, k) = f (i, j, k − 1)
◮ Therefore, f (i, j, k) is the minimum of the two quantities
above
Floyd-Warshall Algorithm 6
How Does Floyd-Warshall Work?
◮ We have the following recurrences and base cases
– f (i, j, 0) = cost(i, j)
– f (i, j, k) = min(f (i, k, k − 1) + f (k, j, k − 1), f (i, j, k − 1))
◮ From the values of f (·, ·, k − 1), we can calculate f (·, ·, k)
– It turns out that we don’t need a separate matrix for each k;
overwriting the existing values is fine
◮ That’s how we get Floyd-Warshall algorithm
Floyd-Warshall Algorithm 7
Outline
Floyd-Warshall Algorithm
Dijkstra’s Algorithm
Bellman-Ford Algorithm
Dijkstra’s Algorithm 8
Dijkstra’s Algorithm
◮ Given a directed weighted graph G and a source s
– Important: The edge weights have to be nonnegative!
◮ Outputs a vector d where di is the shortest distance from s to
node i
◮ Time complexity depends on the implementation:
– Can be O(n2 + m), O(m log n), or O(m + n log n)
◮ Very similar to Prim’s algorithm
◮ Intuition: Find the closest node to s, and then the second
closest one, then the third, etc.
Dijkstra’s Algorithm 9
Dijkstra’s Algorithm
◮ Maintain a set of nodes S, the shortest distances to which are
decided
◮ Also maintain a vector d, the shortest distance estimate from s
◮ Initially, S := {s}, and dv := cost(s, v)
◮ Repeat until S = V :
– Find v ∈
/ S with the smallest dv , and add it to S
– For each edge v → u of cost c:
◮ du := min(du , dv + c)
Dijkstra’s Algorithm 10
Outline
Floyd-Warshall Algorithm
Dijkstra’s Algorithm
Bellman-Ford Algorithm
Bellman-Ford Algorithm 11
Bellman-Ford Algorithm
◮ Given a directed weighted graph G and a source s
◮ Outputs a vector d where di is the shortest distance from s to
node i
◮ Can detect a negative-weight cycle
◮ Runs in Θ(nm) time
◮ Extremely easy to code
– Coding time less than a few minutes
Bellman-Ford Algorithm 12
Bellman-Ford Pseudocode
◮ Initialize ds := 0 and dv := ∞ for all v 6= s
◮ For k = 1, . . . , n − 1:
– For each edge u → v of cost c:
◮ dv := min(dv , du + c)
◮ For each edge u → v of cost c:
– If dv > du + c:
◮ Then the graph contains a negative-weight cycle
Bellman-Ford Algorithm 13
Why Does Bellman-Ford Work?
◮ A shortest path can have at most n − 1 edges
◮ At the kth iteration, all shortest paths using k or less edges
are computed
◮ After n − 1 iterations, all distances must be final; for every
edge u → v of cost c, dv ≤ du + c holds
– Unless there is a negative-weight cycle
– This is how the negative-weight cycle detection works
Bellman-Ford Algorithm 14
System of Difference Constraints
◮ Given m inequalities of the form xi − xj ≤ c
◮ Want to find real numbers x1 , . . . , xn that satisfy all the given
inequalities
◮ Seemingly this has nothing to do with shortest paths
– But it can be solved using Bellman-Ford
Bellman-Ford Algorithm 15
Graph Construction
◮ Create node i for every variable xi
◮ Make an imaginary source node s
◮ Create zero-cost edges from s to all other nodes
◮ Rewrite the given inequalities as xi ≤ xj + c
– For each of these constraint, make an edge from j to i with
cost c
◮ Now we run Bellman-Ford using s as the source
Bellman-Ford Algorithm 16
What Happens?
◮ For every edge j → i with cost c, the shortest distance
dvector will satisfy di ≤ dj + c
– Setting xi = di gives a solution!
◮ What if there is a negative-weight cycle?
– Assume that 1 → 2 → · · · → 1 is a negative-weight cycle
– From our construction, the given constraints contain
x2 ≤ x1 + c1 , x3 ≤ x2 + c2 , etc.
– Adding all of them gives 0 ≤ (something negative)
– i.e., the given constraints were impossible to satisfy
Bellman-Ford Algorithm 17
System of Difference Constraints
◮ It turns out that our solution minimizes the span of the
variables: max xi − min xi
◮ We won’t prove it
◮ This is a big hint on POJ 3169!
Bellman-Ford Algorithm 18
