Find the shortest path with Floyd's algorithm
I have an adjacency matrix that contains the number 0s and 1s. If there is no edge from one node to another, the field will be 0, otherwise the field will be marked as 1.
Then, if the field in the adjacency matrix is 0, there is no edge between the nodes, otherwise there is an edge with weight 1.
Now I have applied Floyd's algorithm to find out the shortest path from any node to each other node. But I am not getting the right solution.
Here is my implementation of Floyd's algorithm.
void Floyd_Warshal(int graph[Nodes][Nodes], int D[Nodes][Nodes])
{
for (int i = 0; i < Nodes; i++)
{
for (int j = 0; j < Nodes; j++)
{
if (graph[i][j] == 0) { graph[i][j] = INT_MAX; }
D[i][j] = graph[i][j];
}
}
for (int k = 0; k < Nodes; k++) {
for (int i = 0; i < Nodes; i++)
{
for (int j = 0; j < Nodes; j++)
{
if (D[i][j] > D[i][k] + D[k][j]) {
D[i][j] = D[i][k] + D[k][j];
}
}
}
}
}
I set 0 as INT_MAX
in order to plot the standard matrix for the algorithm, but I didn't get the right solution.
Also, here's an example of my matrix:
A B C D
A 0 0 1 0
B 1 1 0 1
C 0 0 1 0
D 1 0 0 0
After applying the matrix to the algorithm, any 0 in the matrix will be converted to INT_MAX
. I expect to get the weight as 2 or 1, but I get unexpected values like -2712323 ...
source to share
The reason you are getting very large negative values is integer overflow.
If there is no rib, you install D[i][j]=INT_MAX
. But then
if (D[i][j] > D[i][k] + D[k][j]) {
D[i][j] = D[i][k] + D[k][j];
if there is no edge from i
to k
and from k
to j
, then the sum will overflow and the result will be negative. The algorithm will then assume that there is a very short (large negative) path from this i
to that j
, and this will poison all other paths.
I suggest you use INT_MAX/2
instead INT_MAX
.
source to share