#
Bellman-Ford's Shortest Path

/*********************************************************************** * Author: Isai Damier * Title: Bellman-Ford's Single Source Shortest Path * Project: geekviewpoint * Package: algorithm.graph * * Statement: * Given a source vertex and a directed, weighted graph; find the * shortest path between the source vertex and each of the other * vertices. Some of the edges may have negative weights. If the graph * contains any negative weight cycle, throw an exception. * * Time-complexity: O(V*E) * where V is the number of vertices and E is the number of edges. * * The Bellman-Ford Strategy: * * The Bellman-Ford argument is that the longest path in any graph * can have at most V-1 edges, where V is the number of vertices. * Furthermore, if we perform relaxation on the set of edges once, then * we will at least have determined all the one-edged shortest paths; * if we traverse the set of edges twice, we will have solved at least * all the two-edged shortest paths; ergo, after the V-1 iteration thru * the set of edges, we will have determined all the shortest paths * in the graph. * * But then Bellman-Ford continues: If after V-1 iterations we are still * able to relax any path, then the graph has a negative edge cycle. * * From that argument, even before looking at any code, we can see * that the time complexity is (V-1)*E +1*E = V*E. The 1*E is the * cycle-detection pass. * * The argument also implicitly tells us that this algorithm does not * mind handling negatives edges -- only negative cycles are scary. * * Hence, while Bellman-Ford takes longer than all versions of * Dijkstra's algorithm, it has the advantage of accepting all * directed graphs. * * I use the term relaxation a few times. Here is the explanation. * The computation starts by estimating that all vertices are infinitely * far away from the source vertex. Then as we compute, we relax that * outrageous assumption by checking if there is actually a shorter * distance. For instance, say we have already computed the shortest * distance from s to v as sv and now we are seeking the solution from * s to x, where x is adjacent to v. Then we know sx <= sv + vx; which * simply means, either the path from s to v to x is the shortest path * or there is yet a shorter path than that. If however we find that * our "outrageous" estimate so far is that sx > sv+vx, then we can * set sx = sv+vx as our new better estimate. That's it. That's * relaxation. **********************************************************************/ package algorithm.graph; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class BellmanFord { public Integer[][] singleSourceShortestPath(Integer[][] weight, int source) throws Exception { //auxiliary constants final int SIZE = weight.length; final int EVE = -1;//to indicate no predecessor final int INFINITY = Integer.MAX_VALUE; //declare and initialize pred to EVE and minDist to INFINITY Integer[] pred = new Integer[SIZE]; Integer[] minDist = new Integer[SIZE]; Arrays.fill(pred, EVE); Arrays.fill(minDist, INFINITY); //set minDist[source] = 0 because source is 0 distance from itself. minDist[source] = 0; //relax the edge set V-1 times to find all shortest paths for (int i = 1; i < minDist.length - 1; i++) { for (int v = 0; v < SIZE; v++) { for (int x : adjacency(weight, v)) { if (minDist[x] > minDist[v] + weight[v][x]) { minDist[x] = minDist[v] + weight[v][x]; pred[x] = v; } } } } //detect cycles if any for (int v = 0; v < SIZE; v++) { for (int x : adjacency(weight, v)) { if (minDist[x] > minDist[v] + weight[v][x]) { throw new Exception("Negative cycle found"); } } } Integer[][] result = {pred, minDist}; return result; } /****************************************************************** * Retrieve all the neighbors of vertex v. *****************************************************************/ private List<Integer> adjacency(Integer[][] G, int v) { List<Integer> result = new ArrayList<Integer>(); for (int x = 0; x < G.length; x++) { if (G[v][x] != null) { result.add(x); } } return result; } }

package algorithm.graph; import org.junit.Test; import static org.junit.Assert.*; public class BellmanFordTest { public BellmanFordTest() { } @Test public void testBellmanFordWithPositiveEdges() throws Exception { System.out.println("singleSourceShortestPath"); Integer[][] weight = { {null, 10, null, null, 3}, {null, null, 2, null, 1}, {null, null, null, 7, null}, {null, null, 9, null, null}, {null, 4, 8, 2, null} }; int source = 0; BellmanFord instance = new BellmanFord(); Integer[][] expResult = {{-1, 4, 1, 4, 0}, {0, 7, 9, 5, 3}}; Integer[][] result = instance.singleSourceShortestPath(weight, source); assertArrayEquals(expResult, result); } @Test public void testBellmanFordWithNegativeEdges() throws Exception { System.out.println("singleSourceShortestPath"); Integer[][] weight = { {null, -1, 4, null, null}, {null, null, 3, 2, 2}, {null, null, null, null, null}, {null, 1, 5, null, null}, {null, null, null, -3, null} }; int source = 0; BellmanFord instance = new BellmanFord(); Integer[][] expResult = {{-1, 0, 1, 4, 1}, {0, -1, 2, -2, 1}}; Integer[][] result = instance.singleSourceShortestPath(weight, source); assertArrayEquals(expResult, result); } @Test public void testBellmanFordWithNegativeCycle() { System.out.println("singleSourceShortestPath"); Integer[][] weight = { {null, -1, 4, null, null}, {null, null, 3, 2, 2}, {null, -6, null, null, null}, {null, 1, 5, null, null}, {null, null, null, -3, null} }; int source = 0; BellmanFord instance = new BellmanFord(); try { instance.singleSourceShortestPath(weight, source); fail("Should have thrown an exception: Negative weight cycle"); } catch (Exception ex) { assertTrue(true); } } }