java - Floyd Warshall算法实现

Question

我已经为一个 100 x 100 的邻接矩阵编写了代码，它表示以下有向图:

我正在尝试使用 Floyd-Warshall 算法为图中所有蓝色节点对找到最短路径。你如何只找到所选节点的所有对最短路径？这是我到目前为止编写的代码:

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

Answer 1

首先，不要在floydWarshall()中给adjMat参数赋新值，因为退出后该值不会被保存。

下一步是检查 adjMat[i][k] 和 adjMat[k][j] 是否与 INF 相等，如果是则继续循环:

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