BellMan Ford vs Floyd Warshall (graph problem 12) [solved]

Question : “https://www.e-olymp.com/en/problems/1453

My approach apply bellman and print min distance from 1 to every other, and it passed too, but when I did the same question with Floyd Warshall it gave me WA in some TC’s.

code - “https://ideone.com/4RgVFP

Help @ssjgz @galencolin @aneee004 @everule1 @aryan12

Both are Dynamic programming approach , If I used Dijikstra and if it give WA then I understand as it is greedy algo , but why this shows WA ?

Help krdo @everule1 @ay2306

You read in the graph incorrectly for the DP array:

that can contain multiple edges

You need to do

dp[x][y] = min(dp[x][y], cost);

Furthermore:

  1. use typedef instead of #define for defining type aliases. Here is why
  2. Using vector is often more beneficial in terms of debugging, code quality etc.
lli dp[n][n];
loop(i, n) {
    loop(j, n) {
        if (i == j)
            dp[i][j] = 0;
        else
            dp[i][j] = INF;
    }
}

Can be simplified to

typedef vector<int> vi;
typedef vector<vi> vvi;

vvi dp(n, vi(n,INF));
for (int i = 0; i < n; i++) {
    dp[i][i] = 0;
}

And there are compiler flags which enable out of bounds access checks in vector; you don’t have those for array. Any problem where using array gets AC and vector gets TLE are improperly set; both structures have the same time complexity.

  1. In the reading phase you have dp[x][x] = 0; dp[y][y] = 0; this has already been done by the previous initialization.
5 Likes

:+1:

(though I always find C++11’s using to be clearer :slight_smile:

using vi = vector<int>;
using vii = vector<vi>;

)

:+1:

:+1:

2 Likes

I did this too let me do again.

Oh yes , It works , My bad :slightly_frowning_face:

Ok , next time I will use this , thank you very much @spaanse

1 Like

Hey I was trying this as well but could debug mine. If your works can you tell me where I am wrong. Thank you :sweat_smile:

Code

#include<bits/stdc++.h>
using namespace std;
int dp[110][110];
const int inf = 1e9;
int main(){
    int n,m,a,b,d;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            dp[i][j] = (i == j ? 0 : inf);
    while(m--){
        scanf("%d%d%d",&a,&b,&d);
        dp[a][b] = min(dp[a][b],d);
    }
    for(int k = 1; k <= n; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                if(dp[i][k] < inf && dp[k][j] < inf)
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
    for(int i = 1; i <= n; ++i)printf("%d ",dp[1][i]);
    return 0;
}

I did not know that exists, indeed the syntax is cleaner. As it does exactly the same as typedef I won’t change my c++ init snippet.

4 Likes

if DP[i][j] == INF then print 30000

u solved @ay2306 ?

Not received mail for account verification from that site :rofl:

1 Like

:rofl:

1 Like

one more doubt let say we have undirected +ve weighted tree , Now we have to Find two vertices the distance between which is minimum , not need to print vertices just print distance , so what we can do is -

    lli dp[n][n];
    loop(i,n)
        {
            loop(j,n)
            {
                if(i==j)
                    dp[i][j]=0;
                else
                    dp[i][j] = INF;
            }
        }
    loop(i,m)
    {
        lli x,y,cost;
        cin>>x>>y>>cost;
        --x;
        y--;
        dp[x][y] = cost;
        dp[y][x] = cost;
    }

    loop(k,n)
    {
        loop(i,n)
        {
            loop(j,n)
            {
                dp[i][j] = min(dp[i][j] , dp[i][k]+dp[k][j]);
            }
        }
    }

lli ans = INF;
loop(i,n)
   loop(j,n)
       if(i!=j)
           ans = min(ans , dp[i][j])

print(ans);

But what if we have to find the maximum distance , I did by taking -INF but not correct answer.
@ssjgz @spaanse

I believe the following will work, if the time limit accepts \mathcal{O}(n^3):

... floyd warschall
lli ans = 0;
loop(i,n)
    loop(j,n)
        ans = max(ans,dp[i][j]);
print(ans);

Otherwise use the algorithm for finding a graph diameter.

It find the minimum path right ?

But I want max path so can u please tell me the code for floyd warshall for MAX path

Yes , N3 is too much and not allowed too , but i just did floyd warshall for min path but don’t figure out for max path.

That is the thing, in a tree the minimum simple path between any two vertices is also the maximum simple path between those vertices. Because there are no cycles there is exactly one path between each pair of vertices.

Oh shit man , I always mistake in graph vs tree :weary: , BTW what if it is graph then how the conditions will change please tell.

For the general graph using floyd warschall is one of the best algorithms.