# Warshall-Floyd All-To-All Shortest Pathby 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 {

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

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);
}
}
}
}
}```