## floyd warshall

in java

### Source Code

``````/*
* The Floyd-Warshall algorithm is used to find the shortest path between
* all pairs of nodes in a weighted graph with either positive or negative
* edge weights but without negative edge cycles.
*
* The running time of the algorithm is O(n^3), being n the number of nodes in
* the graph.
*
* This implementation is self contained and has no external dependencies. It
* does not try to be a model of good Java OOP, but a simple self contained
* implementation of the algorithm.
*/

import java.util.Arrays;

public class FloydWarshall {

// graph represented by an adjacency matrix
private double[][] graph;

private boolean negativeCycle;

public FloydWarshall(int n) {
this.graph = new double[n][n];
initGraph();
}

private void initGraph() {
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph.length; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = Double.POSITIVE_INFINITY;
}
}
}
}

public boolean hasNegativeCycle() {
return this.negativeCycle;
}

public void addEdge(int from, int to, double weight) {
graph[from][to] = weight;
}

// all-pairs shortest path
public double[][] floydWarshall() {
double[][] distances;
int n = this.graph.length;
distances = Arrays.copyOf(this.graph, n);

for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
distances[i][j] = Math.min(distances[i][j], distances[i][k] + distances[k][j]);
}
}

if (distances[k][k] < 0.0) {
this.negativeCycle = true;
}
}

return distances;
}

}
``````
``````import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;
import org.junit.Assert;

import java.util.Arrays;

@RunWith(JUnit4.class)
public class FloydWarshall_test {

@Test
public void basicTest() {
FloydWarshall fw = new FloydWarshall(4);
double INF = Double.POSITIVE_INFINITY;
double[][] expected ={ {0,   5,   8,   9},
{INF, 0,   3,   4},
{INF, INF, 0,   1},
{INF, INF, INF, 0} };

double[][] result = fw.floydWarshall();
String errorMsg = String.format("Failure - Expected: %s Got: %s", Arrays.deepToString(expected),
Arrays.deepToString(result));
Assert.assertArrayEquals(errorMsg, expected, result);
}

@Test
public void negativeWeights() {
FloydWarshall fw = new FloydWarshall(4);
double INF = Double.POSITIVE_INFINITY;
double[][] expected ={ {0,   1,   -2,    1},
{INF, 0,   INF,   3},
{INF, INF, 0,     3},
{INF, INF, INF,   0} };

double[][] result = fw.floydWarshall();
String errorMsg = String.format("Failure - Expected: %s Got: %s", Arrays.deepToString(expected),
Arrays.deepToString(result));
Assert.assertArrayEquals(errorMsg, expected, result);
}

@Test
public void detectsNegativeCycles() {
FloydWarshall fw = new FloydWarshall(1);
double[][] expected = new double[1][1];
expected[0][0] = -2;