java - 所有对最短路径问题

Question

我编写了这个程序，它使用邻接矩阵实现了一个包含 100 个节点的图。我还使用了 Floyd-Warshall 算法来查找所有 100 个节点的所有对最短路径。现在，我想将 100 x 100 矩阵压缩为 10 x 10 矩阵，其中仅包含 public static final int A = 100 指定的 10 个索引的所有对最短路径。 .public static final int W = 66。我应该如何压缩数组？我已经开始构造一个名为 arrayCondenser 的新方法，但是否有更简单的方法来实现这一点？

public class AdjacencyMatrix
{       
    public static final int NUM_NODES = 100;
    public static final int INF = 99999;

    public static final int A = 20;
    public static final int B = 18;
    public static final int C = 47;
    public static final int D = 44;
    public static final int E = 53;
    public static final int F = 67;
    public static final int G = 95;
    public static final int H = 93;
    public static final int I = 88;
    public static final int W = 66;

    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 static int[][] floydWarshall(int[][] adjMat, int N)
    {
        adjMat = new int[N][N];
        initialize(adjMat, N);

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

        return adjMat;
    }

    public static int[][] arrayCondenser(int[][] adjMat, int N)
    {
        int[] array = {A,B,C,D,E,F,G,H,I,W};
        adjMat = floydWarshall(adjMat, N);




        return adjMat;
    }

    public static void printGrid(int[][] adjMat)
    {
        for (int i=0; i<NUM_NODES; ++i)
        {
           for (int j=0; j<NUM_NODES; ++j)
           {
               if (adjMat[i][j]==INF)
                   System.out.printf("%5s", "INF");
               else
                   System.out.printf("%5d",adjMat[i][j]);
           }
           System.out.println();
        }
    }

    public static void main(String[] args)
    {

        int adjMat[][] = new int[NUM_NODES][NUM_NODES];
        adjMat = floydWarshall(adjMat, NUM_NODES);

        printGrid(adjMat);            

        System.out.println();
    }
}

Answer 1

我认为您尝试做的事情是不可能的。 Floyd-Warshall 算法迭代地(如您所知)考虑使用先前顶点的每条最短路径。删除顶点(并通过代理、边)后，您将删除可能包含或不包含这些顶点的最短路径的有效场景。

一旦更改了所使用的顶点集，就必须重新计算新图形的最短路径。否则，您基本上必须跟踪每条路径，以便在删除顶点时，可以删除使用这些顶点的任何路径 - 从而获得新的最短路径。