Need Programming Assignment Help?

Get Help with Programming Assignment in Java, C/C++, Dot Net, PHP, Database and UML Diagrams

Floyd-Warshall Algorithm

Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.

public static int[][] floydWarshall(int[][] d) {
    int[][] p = constructInitialMatixOfPredecessors(d);
    for (int k = 0; k < d.length; k++) {
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d.length; j++) {
                if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) {
                    continue;                  
                }
                
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    p[i][j] = p[k][j];
                }

            }
        }
    }
    return p;
}


private static int[][] constructInitialMatixOfPredecessors(int[][] d) {
    int[][] p = new int[d.length][d.length];
    for (int i = 0; i < d.length; i++) {
        for (int j = 0; j < d.length; j++) {
            if (d[i][j] != 0 && d[i][j] != Integer.MAX_VALUE) {
                p[i][j] = i;
            } else {
                p[i][j] = -1;
            }
        }
    }
    return p;
}