CODEWITHSUNDEEP
c++algorithmgraphshortest-pathfloyd-warshall
VCL_D
VCL_D

Reputation: 43

Find the shortest path with Floyd algorithm

I have an adjacency matrix which contains a number 0s and 1s. If there is no edge from one node to another, the field will 0, otherwise the field will marked as 1.

Then, if a field in the adjacency matrix was 0, there is no edge between nodes, otherwise there is an edge with weight of 1.

Now, I have applied Floyd algorithm to find out the shortest path from any node to each other node. But I don't get the right solution.

Here is my Floyd algorithm implementation.

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 have set the 0's as INT_MAX in order to build the standard matrix for the algorithm but I didn't get the right solution.

Also, here is 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 the INT_MAX. I expect to get the weight as 2's or 1's but I get unexpected values such as -2712323...

Upvotes: 3

Views: 1106

Answers (1)

Petr
Petr

Reputation: 9997

The reason why you get very big negative values is integer overflow.

If there is no edge, you set 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. Afterwards, you algorithm will think that there is a very short (large negative) path from this i to this j, and this will poison all other paths.

I suggest you using INT_MAX/2 instead if INT_MAX.

Upvotes: 5

Related Questions