/*************************************************************************
* 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);
}
}
}
}
}