Warshall-Floyd All-To-All Shortest Path
by Isai Damier, Android Engineer @ Google

/*************************************************************************
 * Author: Isai Damier
 * Title: Warshall-Floyd All-To-All Shortest Path
 * Project: geekviewpoint
 * Package: algorithms.graph
 *
 * Statement:
 *   In the given graph, find the shortest path from any vertex v to any
 *   other vertex u.
 *
 * Time Complexity of Solution:
 *   Best = Average = Worst = O(n^3).
 *
 * Input: The input graph is represented as a weighted adjacency matrix,
 *   Where weight[v][x] == null indicates no edge between v and x.
 *
 * Output: The output of this function is a list, List<Integer[]>.
 *    Each element of this list is an array of the form
 *    {v, x, distance from v to x, predecessor of x}.
 *
 * Description: Given a graph, this algorithm returns a list detailing the
 *   shortest path from any vertex to any other vertex: hence the name
 *  "all pairs shortest path." Each element of the list to be returned is
 *   an array presented as {v, x, distance from v to x, predecessor of x}.
 *   For example {1,9,14,4} would mean: the distance from vertex 1 to
 *   vertex 9 is 14 units, taking route 4 to 9.
 *
 * Technical Details: As with most graph algorithms this is a
 *    dynamic algorithm, which means the result is continuously
 *    adjusted until the desired extremum. This algorithm in
 *    particular is easy to analyze. The core algorithm comprises
 *    three for loops:
 *
 *       for(t = 1 to graph size)
 *         for(v = 1 to graph size)
 *           for(x = 1 to graph size)
 *             if(dist[v][x] > dist[v][t]+weight[t][x])
 *               dist[v][x] = dist[v][t]+weight[t][x];
 *
 *    Therefore the time complexity is simply O(n^3).
 *
 *    In addition to the core algorithm, the following are needed
 *    to complete implementation:
 *
 *    0] Declare pred to track path between vertices; and dist
 *       to compute minimum distances between vertices.
 *    1] Initialize dist with 0 on diagonals to indicate that a
 *       vertex is 0 distance from itself; INFINITY where no edge
 *       exists; dist[v][x] = weight[v][x] for all other edges.
 *       Accordingly, Initialize pred with -1 where dist is 0 or
 *       INFINITY; and with v where dist[v][x]=weight[v][x].
 *
 *   Unlike some other algorithms on weighted graphs, all-to-all
 *   accepts negative weights.
 *
 *   The presented implementation can also be used to detect
 *   cycles. Just leave the diagonals initialized to INFINITY.
 *   After running the function, if any of the diagonals
 *   in dist is not INFINITY, then the graph contains a cycle.
 *
 ************************************************************************/ 
 
import java.util.ArrayList;
import java.util.List;

public class WarshallFloydAllToAllShortestPath {

  public List<Integer[][]> allPairsShortestPath(Integer[][] weight) {
    //auxiliary constants
    final int n = weight.length;
    final Integer EVE = -1;
    final Integer INFINITY = Integer.MAX_VALUE;
    //declare pred and dist
    Integer[][] pred = new Integer[n][n];
    Integer[][] dist = new Integer[n][n];
    //intialize pred and dist
    for (int v = 0; v < n; v++) {
      for (int x = 0; x < n; x++) {
        dist[v][x] = INFINITY;
        pred[v][x] = EVE;
      }
      dist[v][v] = 0;//if wishing to detect cycles, set to INFINITY instead
      for (int x = 0; x < n; x++) {
        if (null != weight[v][x]) {
          dist[v][x] = weight[v][x];
          pred[v][x] = v;
        }
      }
    }// end for: initialize

    //dynamically find the shortest distance between each pair.
    for (int t = 0; t < n; t++) {
      for (int v = 0; v < n; v++) {
        for (int u = 0; u < n; u++) {
          if (dist[v][u] > (long) dist[v][t] + dist[t][u]) {
            dist[v][u] = dist[v][t] + dist[t][u];
            pred[v][u] = pred[t][u];
          }
        }
      }
    }
    List<Integer[][]> labels = new ArrayList<>();
    labels.add(pred);
    labels.add(dist);
    return labels;
  }
}
package algorithms.graph;

import java.util.List;
import org.junit.After;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;

public class WarshallFloydAllToAllShortestPathTest {

  WarshallFloydAllToAllShortestPath warshallFloyd;

  @Before
  public void setUp() throws Exception {
    warshallFloyd = new WarshallFloydAllToAllShortestPath();
  }

  @After
  public void tearDown() throws Exception {
    warshallFloyd = null;
  }

  /**
   * Test of allPairsShortestPath method, of class WarshallFloydAllToAllShortestPath.
   */
  @Test
  public void testAllPairsShortestPath() {
    final int INFINITY = Integer.MAX_VALUE;
    Integer[][] G = {
      {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[][] expPred = {
      {-1, 4, 1, 4, 0},
      {-1, -1, 1, 4, 1},
      {-1, -1, -1, 2, -1},
      {-1, -1, 3, -1, -1},
      {-1, 4, 1, 4, -1}};
    int[][] expDist = {
      {0, 7, 9, 5, 3},
      {INFINITY, 0, 2, 3, 1},
      {INFINITY, INFINITY, 0, 7, INFINITY},
      {INFINITY, INFINITY, 9, 0, INFINITY},
      {INFINITY, 4, 6, 2, 0}};
    List<Integer[][]> result = warshallFloyd.allPairsShortestPath(G);

    for (int i = 0; i < expPred.length; i++) {
      for (int k = 0; k < expPred.length; k++) {
        if (expPred[i][k] != result.get(0)[i][k]) {
          String s = String.format("%d -> %d predecessor mismatch: %d instead of %d",
                  i, k, result.get(0)[i][k], expPred[i][k]);
          fail(s);
        }
      }
    }
    for (int i = 0; i < expDist.length; i++) {
      for (int k = 0; k < expPred.length; k++) {
        if (expDist[i][k] != result.get(1)[i][k]) {
          String s = String.format("%d -> %d distance mismatch: %d instead of %d",
                  i, k, result.get(1)[i][k], expDist[i][k]);
          fail(s);
        }
      }
    }
  }
}