Alle Paare kürzester Weg Ausgabe

Question

Ich habe dieses Programm geschrieben, das ein Diagramm mit 100 Knoten unter Verwendung einer Adjazenzmatrix implementiert. Ich habe auch einen Floyd-Warshall-Algorithmus verwendet, um den kürzesten Pfad aller Paare für alle 100 Knoten zu finden. Nun möchte ich die 100 x 100-Matrix auf eine 10 x 10-Matrix reduzieren, die den kürzesten Pfad aller Paare nur für die 10 von public static final int A = 100 ... public static final int W = 66 angegebenen Indizes enthält. Wie sollte ich das Array verdichten? Ich habe mit der Konstruktion einer neuen Methode namens arrayCondenser begonnen, aber gibt es dafür einen einfacheren Weg?

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

Ich glaube nicht, was Sie versuchen zu tun ist möglich. Der Floyd-Warshall-Algorithmus betrachtet iterativ (wie Sie wissen) jeden kürzesten Pfad unter Verwendung der vorherigen Knoten. Sobald Sie die Scheitelpunkte (und den Proxy, die Kanten) entfernt haben, entfernen Sie die gültigen Szenarios für den kürzesten Pfad, die diese Scheitelpunkte enthalten können oder auch nicht.

Sobald Sie den von Ihnen verwendeten Scheitelpunktsatz geändert haben, müssen Sie die kürzesten Pfade für Ihren neuen Graphen neu berechnen. Andernfalls müssten Sie im Prinzip jeden einzelnen Pfad verfolgen, sodass Sie beim Entfernen von Scheitelpunkten alle Pfade entfernen könnten, die diese Scheitelpunkte verwendet haben - und somit die kürzesten Pfade haben.