Floyd Warshall algorithm implementation

Question

I've written code for a 100 x 100 adjacency matrix that represents the following directed graph:

I'm attempting to use a Floyd-Warshall algorithm to find the shortest path for all pairs of blue nodes in the graph. How do you only find the all pairs shortest path for the selected nodes? Here's the code I've written thus far:

public class AdjacencyMatrix
{       
    public static final int NUM_NODES = 100;
    public static final int INF = Integer.MAX_VALUE;
    
    public static boolean even(int num) 
    {
        return num%2==0;
    }

    public static boolean odd(int num) 
    {
        return num%2==1;
    }

    public static void initialize(int [][] adjMat, int N) 
    {
        for(int i = 0; i < N; i++)
            for(int j = 0; j <N; j++)
                adjMat[i][j]=INF;

        for(int x = 0; x<N; x++)
        {
            int row = x/10;
            int column = x%10;

            if (even(row)) {
                if (column!=9)
                    adjMat[x][x+1]=1;
            }
            if (odd(row)) {
                if (column!=0)
                    adjMat[x][x-1]=1;
            }
            if (even(column)){
                if (row!=9)
                    adjMat[x][x+10]=1;
            }
            if (odd(column)) {
                if (row!=0)
                    adjMat[x][x-10]=1;
            }
        }
    }
    
    public void floydWarshall(int[][] adjMat, int N)
    {
    	adjMat = new int[N][N];
	    initialize(adjMat, NUM_NODES);

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

    }

    public static void main(String[] args)
    {

        int adjMat[][] = new int[NUM_NODES][NUM_NODES];
        initialize(adjMat, NUM_NODES);
        
        int A,B,C,D,E,F,G,H,I,W;
        
        A = 20;
        B = 18;
        C = 47;
        D = 44;
        E = 53;
        F = 67;
        G = 95;
        H = 93;
        I = 88;
        W = 66;
       
        System.out.println(adjMat[A][B]);

        System.out.println();
    }
}

Nolequen Nolequen · Accepted Answer · 2017-03-06T19:14:59

First of all, you should not assign new value to adjMat parameter in floydWarshall(), because the value will not be saved after exiting the method.

The next step is to check adjMat[i][k] and adjMat[k][j] for equality to INF and continue the loop if so:

for(int k = 0; k < N; ++k) {
   for(int i = 0; i < N; ++i) {
      for(int j = 0; j < N; ++j) {
        if (adjMat[i][k] != INF && adjMat[k][j] != INF) {
            adjMat[i][j] = Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
        }

Floyd Warshall algorithm implementation

2 Answers