Floyd-warshall für die längste Entfernung für ungerichtete Graphen

Question

Ich möchte den größten Abstand zwischen zwei beliebigen Ecken eines gewichteten ungerichteten Graphen mit Floyd-Warsshall-Algorithmus finden. Dazu habe ich einige Änderungen vorgenommen:

1. Ich füge negative Gewichte statt positiv.

2. Dann finde ich den kürzesten Weg.

Aber es gibt mir nicht die richtige Ausgabe. Kann jemand auf den Fehler hinweisen, den ich mache?

class TestClass { 
    public static void main(String args[]) throws Exception { 
     Scanner sc = new Scanner(System.in); 
     int testcases=sc.nextInt(); 
     for(int t=0;t<testcases;t++) 
     { 
      int nodes=sc.nextInt(); 
      int edges=sc.nextInt(); 
      int[][] dist_mat=new int[nodes][nodes]; 
      for(int i=0;i<nodes;i++) 
      { 
       for(int j=0;j<nodes;j++) 
       { 
        if(i!=j) 
        { 
         dist_mat[i][j]=Integer.MAX_VALUE; 
        } 
       } 
      } 
      for(int i=0;i<edges;i++) 
      { 
       int source=sc.nextInt(); 
       int dest=sc.nextInt(); 
       dist_mat[source-1][dest-1]=-sc.nextInt(); 
       dist_mat[dest-1][source-1]=dist_mat[source-1][dest-1]; 
      } 

      for(int k=0;k<nodes;k++) 
      { 
       for(int i=0;i<nodes;i++) 
       { 
        for(int j=0;j<nodes;j++) 
        { 

         if(i!=j && j!=k && i!=k && dist_mat[i][j]>dist_mat[i][k]+dist_mat[k][j]) 
         { 
          if(dist_mat[i][k]<Integer.MAX_VALUE && dist_mat[k][j]<Integer.MAX_VALUE) 
            dist_mat[i][j]=Integer.min(dist_mat[i][j],dist_mat[i][k]+dist_mat[k][j]); 
          if(dist_mat[j][k]<Integer.MAX_VALUE && dist_mat[k][i]<Integer.MAX_VALUE) 
            dist_mat[j][i]=Integer.min(dist_mat[j][i],dist_mat[j][k]+dist_mat[k][i]); 
         } 

        } 
       } 
      } 
     } 
    } 

Der gleiche Eingang ist: -

1 [Anzahl der Testfälle]

5 4 [Anzahl der Knoten, die Anzahl der Kanten]

1 2 4 [erster Knoten, zweiter Knoten, Gewicht]

3 2 3 [erster Knoten, zweiter Knoten, Gewicht]

2 5 2 [erste Knoten, zweiter Knoten, Gewicht]

4 1 1 [erster Knoten, zweiter Knoten, Gewicht]

Answer 1

Ein Algorithmus, der verwendet werden könnte, einen längsten Pfad zwischen zwei beliebigen Knoten des Finden der Lage sein würde, das Hamiltonian path Problem, zu entscheiden, . Das Hamilton-Pfadproblem ist jedoch NP-complete. Der Floyd-Warshall-Algorithmus ergibt eine polynomiale Laufzeitgrenze, daher ist es im Gegensatz zu einer Modifikation, die zu einem Algorithmus führt, der die längsten Pfade bestimmt.