0

I'm trying to write a program that uses a DIMACS Graph input, and do several diffent things with it. I've got most of the methods working except one: An all-pairs shortest path that uses Floyd's Algorithm. I've written it a couple times, and it works sometimes, throws and exception sometimes, and gets stuck in an infinite loop sometimes :cry: I've followed every single note and algorithm, and yet it still doesn't work.

I'm pretty sure the problem is related to the Path[][] variable that it returns. Any help would be much appreciated :mrgreen:

```
private static void floyd(Graph<City> g, double dist[][], int path[][]) throws GraphException
{
int i;
int j;
int k;
City c1;
City c2;
for( i =0; i < g.size(); i++) {
c1 = g.retrieveVertex(new City(i+1));
for(j = 0; j < g.size(); j++) {
c2 = g.retrieveVertex(new City(j+1));
path[i][j] = 0;
if ( i == j)
dist[i][j] = 0;
else if(g.isEdge(c2, c1) == true)
dist[i][j] = g.retrieveEdge(c1, c2);
else
dist[i][j] = INFINITY;
}
}
for(k = 0; k < g.size(); k ++) {
for( i = 0; i < g.size(); i++) {
for(j = 0; j < g.size(); j++) {
if (dist[i][k] != INFINITY && dist[k][j] != INFINITY) {
if (dist[i][j] >(dist[i][k] + dist[k][j])) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k;
}
}
}
}
}
}
```