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

help
7

Oh yes , It works , My bad :slightly_frowning_face:

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

1 Like
8

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;
}
9

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
10

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

11

u solved @ay2306 ?

12

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

1 Like
13

:rofl:

1 Like
14

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

15

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.

16

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

17

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.

18

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.

19

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.

20

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

21

for max path ? @spaanse

22

For the longest minimum distance between any pair of nodes

23

nope for maximum path in graph .

24

Well, that is a lot more difficult. An algorithm for that does exist in a directed acyclic graph but I don’t know any for a general graph

25

Both are dynamic approach.
File Handling in C Language

26

wrong thread?