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

It doesn't look like you undid anything.

Nate
– Nate

2017-03-05 23:50:58 +00:00
Commented Mar 5, 2017 at 23:50 — Nate
– Nate, Commented Mar 5, 2017 at 23:50

Nolequen · Accepted Answer · 2017-03-06 19:14:59Z

2

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

answered Mar 6, 2017 at 19:14

Nolequen

4,7078 gold badges49 silver badges66 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Andreikkaa · Accepted Answer · 2017-03-07 00:23:00Z

0

Shortest Floyd-Warshall algo implemenation:

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

After running this piece of cade adjMat will contain shortest distances between every pair of nodes.

Update: to avoid integer overflow, fill the matrix with Integer.MAX_VALUE / 2. In general case, it's dangerous to set the maximum possible value to variable as infinity, because you can't perform addition operation with it.

edited Mar 7, 2017 at 0:23

answered Mar 5, 2017 at 22:44

Andreikkaa

2971 silver badge7 bronze badges

5 Comments

Nate Over a year ago

I've added your code to the floydWarshall() method, but it's ouputting a matrix of all 0's.

Nate Over a year ago

I'm still not getting this code to output properly. It looks like the logic is correct, so I'm not sure what's going wrong.

Petar Petrovic Over a year ago

I am not familiar with java, but will adjMat[i][k] + adjMat[k][j] overflow if one term is Intmax?

Daniel Over a year ago

you must remember you have to clean the matrix first. The first step is to set all matrix' values to infinite (very big value), and then, set all diagonal values to 0. This should do the job: for(int i = 0; i < size; i++) for(int j = 0; j < size; j++) M[i][j] = (i == j? 0 : 99999999);, then you run the FW algorithm just as described above.

Andreikkaa Over a year ago

Not really, I'm working with matrix that represents a graph.

Collectives™ on Stack Overflow

Floyd Warshall algorithm implementation

2 Answers 2

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related