floyd warshall


See On Github

Data

Contributor

Generic placeholder thumbnail

by dalleng

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

    // utility function to add edges to the adjacencyList
    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} };
        fw.addEdge(0, 1, 5);
        fw.addEdge(0, 2, 9);
        fw.addEdge(0, 3, 10);
        fw.addEdge(1, 2, 3);
        fw.addEdge(2, 3, 1);

        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} };
        fw.addEdge(0, 1, 1);
        fw.addEdge(0, 2, -2);
        fw.addEdge(1, 3, 3);
        fw.addEdge(2, 3, 3); 

        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;
        fw.addEdge(0, 0, -1);

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

}