Problem on a Floyd-Warshall implementation using c++

Question

I've got a assignment for my college, already implemented Dijkstra and Bellman-Ford sucessfully, but i'm on trouble on this one. Everything looks fine, but it's not giving me the correct answer.

Here's the 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]);


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

im using this graph example i've made:

6 7

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

means we have 6 vertices (1 to 6), and 7 edges (1,2) with weight 4... etc..

If anyone need more info, i'm up to giving it, just tired of looking at this code and not finding an error.

Answer 1

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

make some check here. e.g. if path[i][k] and path[k][j] are non-infinite, and i!=j i!=k and k!=j.

Answer 2

Nevermind, i took a break to eat something and found out the error.

Infinity is defined as INT_MAX, so as soon as you add something to it, it turns negative.

I only defined to something big (to my problem, like over9000, no graph path will take more than that), and it's working fine.

But may i know why you suggested that Yin? i didn't get that.

Thanks

Answer 3

Also, aren't the starts and ends of your iteration over path off by one in several places? You probably want them running from 0 to nvertices-1; i.e. for (int i = 0; i < nvertices; i++).