Algorithms/floydWarshall.cpp at master · prabhatmalhan/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//Floyd Warshall Undirected Graph

#include <bits/stdc++.h>
#define INF INT_MAX

using namespace std;

#define ll long long

ll **floydWarshall(ll **Graph, ll V)
{
    ll **result = (ll **)malloc(V * sizeof(ll *));
    for (ll i = 0; i < V; ++i)
        result[i] = (ll *)malloc(V * sizeof(ll));

    for (ll i = 0; i < V; ++i)
        for (ll j = 0; j < V; ++j)
            result[i][j] = Graph[i][j];

    for (ll i = 0; i < V; ++i)
        for (ll j = 0; j < V; ++j)
            for (ll k = 0; k < V; ++k)
                if (result[i][k] != INF && result[k][j] && result[i][j] > result[i][k] + result[k][j])
                    result[i][j] = result[i][k] + result[k][j];

    return result;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll V, E;
    cin >> V >> E;

    ll **Graph = (ll **)malloc(V * sizeof(ll *));
    for (ll i = 0; i < V; ++i)
        Graph[i] = (ll *)malloc(V * sizeof(ll));

    for (ll i = 0; i < V; ++i)
        for (ll j = 0; j < V; ++j)
            if (i != j)
                Graph[i][j] = INF;
            else
                Graph[i][j] = 0;

    for (ll i = 0; i < E; ++i)
    {
        ll s, d, w;
        cin >> s >> d >> w;
        Graph[s][d] = w;
        Graph[d][s] = w; //comment to make directed graph
    }
    ll **result = floydWarshall(Graph, V);

    for (ll i = 0; i < V; ++i)
    {
        for (ll j = 0; j < V; ++j)
            if (result[i][j] != INF)
                cout << result[i][j] << "\t";
            else
                cout << "INF"
                     << "\t";
        cout << endl;
    }

    return 0;
}