所有对最短路径问题

我已经编写了这个程序，该程序使用邻接矩阵实现了具有100个节点的图。我还使用Floyd-Warshall算法为所有100个节点找到所有最短路径对。现在，我想将100 x 100矩阵压缩为10 x 10矩阵，该矩阵仅包含public static final int A = 100 ... public static final int W = 66指定的10个索引中的所有配对最短路径。我应该如何压缩阵列？我已经开始构建一种名为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(); 
    } 
}

来源

2017-03-06 Nate

我不认为你想要做什么是可能的。 Floyd-Warshall算法使用以前的顶点迭代地（如你所知）考虑每条最短路径。一旦删除顶点（并通过代理，边），那么您将删除可能包含或不包含这些顶点的最短路径的有效方案。

一旦你改变了你正在使用的顶点集，你将不得不重新计算新图的最短路径。否则，你基本上必须跟踪每一条路径，这样当你删除顶点时，你可以删除任何使用这些顶点的路径 - 从而得到新的最短路径。

来源

2017-03-06 15:59:44 ryuu9187

所有对最短路径问题

回答

相关问题