플로이드 - 마샬링 (floyd-warshall) 무 지향성 그래프에서 가장 긴 거리

Question

Floyd-warshall 알고리즘을 사용하여 가중치가 부여 된 무 방향성 그래프의 두 정점 사이에서 가장 큰 거리를 찾고 싶습니다. 이를 위해 나는 약간의 변경을했습니다 :

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 제 노드 제 노드 무게]

3 2 3 [제 노드 번째 노드 중량]

2~5 2 제 노드 번째 노드 중량]

4 1 1 제 노드 번째 노드 중량]

Answer 1

임의의 두 노드들 사이에서 가장 긴 경로를 발견 할 수있을 것 인 알고리즘 Hamiltonian path 문제를 결정하는데 사용될 수있다 . 그러나 해밀 토니 언 경로 문제는 NP-complete입니다. Floyd-Warshall 알고리즘은 다항식 런타임 경계를 산출합니다. 따라서 가장 긴 경로를 결정하는 알고리즘이 수정 될 것입니다.