Floyd-warshall pour la plus longue distance pour un graphe non orienté

Question

Je veux trouver la plus grande distance entre deux sommets d'un graphe non orienté pondéré en utilisant l'algorithme de Floyd-warshall. Pour cela j'ai fait quelques changements:

1. J'ajoute des poids négatifs au lieu de positif.

2. Ensuite, je trouve le chemin le plus court.

Mais cela ne me donne pas la bonne sortie. Quelqu'un peut-il souligner l'erreur que je fais.

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

        } 
       } 
      } 
     } 
    } 

La même entrée est la suivante: -

1 [nombre de cas de test]

5 4 [nombre de noeuds, le nombre de bords]

1 2 4 [premier noeud, second noeud, le poids]

3 2 3 [premier noeud, le deuxième noeud, le poids]

2 5 2 [premier noeud, le deuxième noeud, le poids]

4 1 1 premier noeud [, second noeud, le poids]

Answer 1

Un algorithme qui serait capable de trouver un chemin plus long entre deux noeuds quelconques peut être utilisé pour déterminer le problème Hamiltonian path . Cependant, le problème du chemin Hamiltonien est NP-complete. L'algorithme de Floyd-Warshall donne une limite d'exécution polynomiale, donc il est différent qu'une modification produise un algorithme qui détermine les chemins les plus longs.