我为一个100x 100邻接矩阵编写了代码,它表示以下有向图:
java - Floyd Warshall算法实现-LMLPHP
我试图使用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();
    }
}

最佳答案

首先,不应该给FuySythHyLar()中的AdjMad参数分配新的值,因为在退出该方法后,该值不会被保存。
下一步是检查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]);
        }

07-26 07:52