/**************************************************************************
* File: BellmanFord.java
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* An implementation of the Bellman-Ford algorithm for single-source shortest
* paths. Like Dijkstra's algorithm, the Bellman-Ford algorithm computes the
* shortest paths from a source node to all other nodes in the graph. However,
* unlike Dijkstra's algorithm, the Bellman-Ford algorithm works correctly in
* graphs containing negative-cost edges, so long as the graph does not contain
* a negative cycle (in which case the cost of a shortest path may not be well-
* defined).
*
* The Bellman-Ford algorithm, like the Floyd-Warshall algorithm, is a classic
* example of a dynamic programming algorithm. The idea behind the algorithm
* is to consider what the shortest path is from the source node s to each
* other node in the graph, subject to the constraint that each path uses no
* more than k edges. When k = n, this contains all acyclic paths in the graph
* and consequently, assuming that there are no negative cycles in the graph,
* must contain the shortest paths in the graph. The rationale behind phrasing
* shortest paths this way is that if we denote by D(t, k) the length of the
* shortest path from the source node s to node t using paths of length at most
* k, it's possible to compute D(t, k) using the following intution. First,
* if we consider the case where k = 0 and all paths must have no edges, then
* we get that
*
* D(t, 0) = +infinity (for t != s)
* D(s, 0) = 0
*
* Since there is no shortest path from s any other node using no edges, while
* the path from s to itself using no edges has length zero.
*
* If we consider the case where k != 0, then there are two ways we could get a
* shortest path from s to some node t using at most k edges. First, it's
* possible that the best way to do this is just to use some path using at most
* k - 1 edges, either since no other paths exist (as would be the case in a
* tree). Alternatively, we could end up with a path of length at most k by
* taking any path of length at most k - 1, then extending it by an edge. For
* each node in the graph, this means that we can compute the value of D(t, k)
* as
*
* D(t, k) = min{ D(t, k - 1), min ((u, t) in E){ D(u, k - 1) + l(u, v)}}
*
* Where l(u, v) denotes the length of the edge (u, v).
*
* This implementation computes this recurrence from the bottom up by beginning
* with k = 0 and progressively increasing it until it reaches |V|.
*
* The runtime of this algorithm is easily determined. We need to compute the
* value of D(t, |V|) for each t, so O(|V|) iterations of the recurrence
* computation are required. On each iteration, for each node, we'll scan the
* outgoing edges from that node, and so each iteration visits each edge
* exactly once. This takes time O(|E|), so the overall runtime is O(|V||E|).
* An interesting detail about this algorithm is that since |E| = O(|V|^2), in
* the worst case this algorithm runs in time O(|V|^3), which is the same
* runtime as the Floyd-Warshall algorithm. However, Floyd-Warshall actually
* produces the lengths of all paths between all pairs of points in this time,
* and so it makes more sense to run Floyd-Warshall rather than Bellman-Ford!
* That said, on sparse graphs (|E| = Theta(|V|)) the runtime is O(|V|^2),
* which is much faster.
*
* The Bellman-Ford algorithm is interesting and useful for several reasons,
* excluding historical relevance. First, the update rule of the Bellman-Ford
* algorithm can be computed in a distributed fashion, making it possible for
* independent computers to each determine their distance from some predefined
* computer using the algorithm. This allows the algorithm to be used in
* network routing protocols. Second, the Bellman-Ford algorithm can be used
* as a subroutine of Johnson's algorithm, an all-pairs shortest paths
* algorithm that is asymptotically faster than the Floyd-Warshall algorithm on
* sparse graphs.
*/
import java.util.*; // For HashMap
public final class BellmanFord {
/**
* Given a directed, weighted graph G and a source node s, produces the
* distances from s to each other node in the graph. If any nodes in
* the graph are unreachable from s, they will be reported at infinite
* distance.
*
* @param graph The graph upon which to run Dijkstra's algorithm.
* @param source The source node in the graph.
* @return A map from nodes in the graph to their distances from the source.
*/
public static <T> Map<T, Double> shortestPaths(DirectedGraph<T> graph, T source) {
/* Construct a map from the nodes to their distances, then populate it
* with the initial value of the recurrence (the source is at distance
* zero from itself; all other nodes are at infinite distance).
*/
Map<T, Double> result = new HashMap<T, Double>();
for (T node: graph)
result.put(node, Double.POSITIVE_INFINITY);
result.put(source, 0.0);
/* Create a new map that acts as scratch space. We'll flip back and
* forth between the result map and this map during each iteration of
* the algortihm so that we avoid needlessly reallocating maps.
*/
Map<T, Double> scratch = new HashMap<T, Double>();
/* Starting with k = 1, compute the new values for the distances by
* evaluating the recurrence.
*/
for (int k = 1; k <= graph.size(); ++k) {
/* Begin by guessing that each node in this new iteration will have
* a cost equal to its cost on the previous iteration.
*/
scratch.putAll(result);
/* Scan across all the edges in the graph, updating the costs of
* the paths of the nodes at their endpoints.
*/
for (T node: graph) {
for (Map.Entry<T, Double> edge: graph.edgesFrom(node).entrySet()) {
/* The new cost of the shortest path to this node is no
* greater than the cost of the shortest path to the nodes'
* neighbor plus the cost of the edge from that neighbor
* into this node.
*/
scratch.put(edge.getKey(), // The node being updated
Math.min(scratch.get(edge.getKey()),
edge.getValue() + result.get(node)));
}
}
/* Finally, exchange the scratch buffer holding the new result with
* the result map holding last iteration's results.
*/
Map<T, Double> temp = result;
result = scratch;
scratch = temp;
}
/* Finally, report the distances. */
return result;
}
}