無指向性グラフの最長距離用Floyd-warshall

Question

Floyd-warshallアルゴリズムを使用して、重み付き無向グラフの任意の2つの頂点間の最大距離を求めたい。このため私はいくつかの変更を加えました：

1. 私はポジティブではなくマイナスの重みを付け加えます。

2. 次に、私は最短経路を見つけます。

しかし、正しい出力は得られません。誰かが私が作っている間違いを指摘できますか？

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

        } 
       } 
      } 
     } 
    } 

同じ入力である： -

1 [テストケースの数]

5 4 [ノードの数、辺の数]

1 2 4 [最初のノード、第2のノード、重量]

3 2 3 [最初のノード、第2ノード、重量]

2 5 2 [第一任意の2つのノード間の最長経路を見つけることができるであろうノード、第2ノード、重量]

4 1 [第一のノード、第2ノード、重量]

Answer 1

アルゴリズムはHamiltonian path問題を決定するために使用することができます。しかし、ハミルトニアン経路の問題はNP-completeです。 Floyd-Warshallアルゴリズムは多項式ランタイム境界を生成します。したがって、変更によって最長パスを決定するアルゴリズムが生成されることはありません。