Problem on a Floyd-Warshall implementation using c++
- by Henrique
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.
