Bug dans mon implémentation C++ de Floyd-Warshall

Question

J'ai un devoir pour mon collège, déjà implémenté avec succès Dijkstra et Bellman-Ford, mais je suis en difficulté sur celui-ci. Tout a l'air bien, mais ça ne me donne pas la bonne réponse.

Voici le code:

void FloydWarshall() 
{ 
    //Also assume that n is the number of vertices and edgeCost(i,i) = 0 

    int path[500][500]; 

    /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path 
     from i to j using intermediate vertices (1..k−1). Each path[i][j] is initialized to 
     edgeCost(i,j) or infinity if there is no edge between i and j. 
    */ 

    for(int i = 0 ; i <= nvertices ; i++) 
     for(int j = 0 ; j <= nvertices ; j++) 
      path[i][j] = INFINITY; 

    for(int j = 0 ; j < narestas ; j++) //narestas = number of edges 
    { 
     path[arestas[j]->v1][arestas[j]->v2] = arestas[j]->peso; //peso = weight of the edge (aresta = edge) 
     path[arestas[j]->v2][arestas[j]->v1] = arestas[j]->peso; 
    } 

    for(int i = 0 ; i <= nvertices ; i++) //path(i, i) = 0 
     path[i][i] = 0; 

    //test print, it's working fine 
    //printf("\n\n\nResultado FloydWarshall:\n"); 
    //for(int i = 1 ; i <= nvertices ; i++) 
    // printf("distancia ao vertice %d: %d\n", i, path[1][i]); 


    // Here's the problem, it messes up, and even a edge who costs 4, and the minimum is 4, it prints 2. 

    //for k = 1 to n 
    for(int k = 1 ; k <= nvertices ; k++) 
     //for i = 1 to n 
     for(int i = 1 ; i <= nvertices ; i++) 
      //for j := 1 to n 
      for(int j = 1 ; j <= nvertices ; j++) 
       if(path[i][j] > path[i][k] + path[k][j]) 
        path[i][j] = path[i][k] + path[k][j]; 


    printf("\n\n\nResultado FloydWarshall:\n"); 
    for(int i = 1 ; i <= nvertices ; i++) 
     printf("distancia ao vertice %d: %d\n", i, path[1][i]); 
} 

J'utilise cet exemple de graphique que j'ai fait:

6 7 

1 2 4 
1 5 1 
2 3 1 
2 5 2 
5 6 3 
6 4 6 
3 4 2 

signifie que nous avons 6 sommets (1 à 6) et 7 bords (1,2) avec le poids 4 ... etc.

Si quelqu'un a besoin de plus d'informations, je suis prêt à le donner, juste fatigué de regarder ce code et ne pas trouver une erreur.

Answer 1

if(path[i][j] > path[i][k] + path[k][j]) 
    path[i][j] = path[i][k] + path[k][j]; 

faites quelques vérifications ici. par exemple. si le chemin [i] [k] et le chemin [k] [j] sont non-infinis, et i! = j i! = k et k! = j.

Answer 2

Peu importe, j'ai pris une pause pour manger quelque chose et j'ai découvert l'erreur.

Infinity est défini comme INT_MAX, de sorte que dès que vous ajoutez quelque chose, il devient négatif.

J'ai seulement défini quelque chose de grand (à mon problème, comme plus de 9000, aucun chemin de graphique n'en prendra plus), et ça fonctionne bien.

Mais puis-je savoir pourquoi vous avez suggéré que Yin? je n'ai pas compris.

Merci

Answer 3

De plus, ne sont pas les débuts et fins de votre itération sur le chemin hors d'un à plusieurs endroits? Vous voulez probablement qu'ils fonctionnent de 0 à nvertices-1; c'est-à-dire for (int i = 0; i < nvertices; i++).