graph and all pairs shortest path in java
- by Sandra
I am writing a java program using Flyod-Warshall algorithm “All pairs shortest path”.
I have written the following :
a0 is the adjacency matrix of my graph, but has infinity instead of 0.
vList is the list of vertexes and the cost for each edge is 1.
Path[i][j] = k+1 means for going from I to j you first go to k then j
int[][] path = new int[size][size];
for(int i = 0; i<path.length;i++)
{
for(int j = 0; j<path.length; j++)
{
if(adjM[i][j]==1)
path[i][j]=j+1;
}
}
//***************
for (int k = 0; k < vList.size(); k++)
for (int i = 0; i < vList.size(); i++)
for (int j = 0; j < vList.size(); j++) {
if (a0[i][j]>a0[i][k]+ a0[k][j])
path[i][j] = k + 1;
a0[i][j] = Math.min(a0[i][j], a0[i][k] + a0[k][j]);
}
After running this code, in the result a0 is correct, but path is not correct and I don’t know why!. Would you please help me?
