CODEWITHSUNDEEP
c++algorithm
Prakhar Shukla
Prakhar Shukla

Reputation: 13

why this algorithm (Floyd Warshal algorithm) only works for 100000007?

This is Floyd Warshal algorithm which i'm using to find the maximum of minimum path in a graph. Why this algorithm don't work if i put INT_MAX or any other big integer like 2147483647 in place of 100000007. 

 int main() {
               int c,f;      //c=number of vertice
                          // f=number of pair of vertices directly connected
               cin >> c >> f;
               int graph[c][c];
               for(int i = 0;i < c;i++)
                       for(int j = 0;j < c;j++)
                               graph[i][j] = 100000007;
               for(int i = 0;i < c;i++)
                       graph[i][i] = 0;
               int x,y,p;
               for(int i = 0;i < f;i++) {
                       cin >> x >> y >> p;
                       graph[x-1][y-1] = p;
                       graph[y-1][x-1] = p;
               }
               int dist[c][c], i, j, k;
               for(i = 0; i < c; i++)
                   for (j = 0; j < c; j++)
                       dist[i][j] = graph[i][j];
               for(k = 0; k < c; k++) {
                     for(i = 0; i < c; i++) {
                           for(j = 0; j < c; j++) {
                                 if(dist[i][k] + dist[k][j] < dist[i][j])
                                               dist[i][j] = dist[i][k] + dist[k][j];
                             }
                      }
               }
               int ans = 0;
               for(int i = 0;i < c;i++)
                       for(int j = 0;j < c;j++)
                               ans = max(ans,dist[i][j]);
               cout << ans << endl;
               return 0;
    }

Upvotes: 0

Views: 110

Answers (1)

Gassa
Gassa

Reputation: 8874

(as in the comments)

Once your value for infinity is greater than INT_MAX / 2, which is 1,073,741,823, the line if(dist[i][k] + dist[k][j] < dist[i][j]) has an overflow in it. Overflow is undefined behavior in C++, but the most likely outcome is that dist[i][k] + dist[k][j] becomes a negative value, and in the next line, dist[i][j] = dist[i][k] + dist[k][j];, actual distances get overwritten by such negative values.

The value you need for infinity should be greater than any real distance you can encounter. If that distance exceeds 230 - 1, consider using a type with higher upper limit (unsigned int32, int64, or even a double).

Upvotes: 1

Related Questions