Johnson's Algorithm

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Johnson's Algorithm implementation using adjacency lists and binary-heap Dijkstra.
5
// - Handles negative edges, detects negative cycles.
6
// - Returns all-pairs shortest path matrix or reports failure.
7
// Graph is 0-indexed.
8
9
struct Edge {
10
    int u, v;          // directed edge u -> v
11
    long long w;       // weight (can be negative)
12
};
13
14
const long long INF = (1LL<<60);
15
16
// Bellman-Ford from a super-source s that has edges (s -> v) of weight 0 for all v.
17
// We implement it by initializing dist[v] = 0 for all v and relaxing all real edges V-1 times.
18
bool bellman_ford_potentials(int n, const vector<Edge>& edges, vector<long long>& h) {
19
    h.assign(n, 0LL); // start as if super-source connects to all with 0; this is equivalent
20
21
    // Relax edges n-1 times
22
    for (int i = 0; i < n - 1; ++i) {
23
        bool changed = false;
24
        for (const auto& e : edges) {
25
            if (h[e.u] != INF && h[e.v] > h[e.u] + e.w) {
26
                h[e.v] = h[e.u] + e.w;
27
                changed = true;
28
            }
29
        }
30
        if (!changed) break; // early stop if no change
31
    }
32
33
    // Check for negative cycle: any further improvement implies a reachable negative cycle
34
    for (const auto& e : edges) {
35
        if (h[e.u] != INF && h[e.v] > h[e.u] + e.w) {
36
            return false; // negative cycle detected
37
        }
38
    }
39
    return true;
40
}
41
42
// Dijkstra on reweighted graph: w'(u,v) = w(u,v) + h[u] - h[v] (non-negative)
43
vector<long long> dijkstra_reweighted(int n, const vector<vector<pair<int,long long>>>& adj, int src) {
44
    vector<long long> dist(n, INF);
45
    dist[src] = 0;
46
    using P = pair<long long,int>; // (distance, node)
47
    priority_queue<P, vector<P>, greater<P>> pq;
48
    pq.push({0, src});
49
50
    while (!pq.empty()) {
51
        auto [d, u] = pq.top(); pq.pop();
52
        if (d != dist[u]) continue; // stale entry
53
        for (auto [v, wprime] : adj[u]) {
54
            if (dist[v] > d + wprime) {
55
                dist[v] = d + wprime;
56
                pq.push({dist[v], v});
57
            }
58
        }
59
    }
60
    return dist;
61
}
62
63
int main() {
64
    ios::sync_with_stdio(false);
65
    cin.tie(nullptr);
66
67
    int n, m;
68
    // Input format:
69
    // n m
70
    // m lines: u v w (0-indexed)
71
    if (!(cin >> n >> m)) {
72
        cerr << "Provide n, m, then m edges (u v w).\n";
73
        return 0;
74
    }
75
    vector<Edge> edges;
76
    edges.reserve(m);
77
    for (int i = 0; i < m; ++i) {
78
        int u, v; long long w; cin >> u >> v >> w;
79
        edges.push_back({u, v, w});
80
    }
81
82
    // 1) Compute potentials h via Bellman-Ford from implicit super-source
83
    vector<long long> h;
84
    if (!bellman_ford_potentials(n, edges, h)) {
85
        cout << "NEGATIVE CYCLE\n";
86
        return 0;
87
    }
88
89
    // 2) Build reweighted adjacency list with non-negative weights
90
    vector<vector<pair<int,long long>>> adj(n);
91
    adj.assign(n, {});
92
    for (const auto& e : edges) {
93
        long long wprime = e.w + h[e.u] - h[e.v];
94
        // Guard: due to correctness, wprime >= 0 if no negative cycles exist
95
        adj[e.u].push_back({e.v, wprime});
96
    }
97
98
    // 3) Run Dijkstra from each source and convert back to original distances
99
    vector<vector<long long>> all(n, vector<long long>(n, INF));
100
    for (int s = 0; s < n; ++s) {
101
        vector<long long> dprime = dijkstra_reweighted(n, adj, s);
102
        for (int v = 0; v < n; ++v) {
103
            if (dprime[v] < INF/2) {
104
                // Convert back: d(s,v) = d'(s,v) - h(s) + h(v)
105
                all[s][v] = dprime[v] - h[s] + h[v];
106
            }
107
        }
108
    }
109
110
    // 4) Output matrix: INF for unreachable pairs
111
    for (int i = 0; i < n; ++i) {
112
        for (int j = 0; j < n; ++j) {
113
            if (all[i][j] >= INF/2) cout << "INF";
114
            else cout << all[i][j];
115
            if (j + 1 < n) cout << ' ';
116
        }
117
        cout << '\n';
118
    }
119
    return 0;
120
}
121

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Edge { int u, v; long long w; };
5
const long long INF = (1LL<<60);
6
7
bool bellman_ford_potentials(int n, const vector<Edge>& edges, vector<long long>& h) {
8
    h.assign(n, 0LL);
9
    for (int i = 0; i < n - 1; ++i) {
10
        bool changed = false;
11
        for (auto &e : edges) {
12
            if (h[e.v] > h[e.u] + e.w) { h[e.v] = h[e.u] + e.w; changed = true; }
13
        }
14
        if (!changed) break;
15
    }
16
    for (auto &e : edges) if (h[e.v] > h[e.u] + e.w) return false; // negative cycle
17
    return true;
18
}
19
20
vector<long long> dijkstra_reweighted(int n, const vector<vector<pair<int,long long>>>& adj, int s) {
21
    vector<long long> d(n, INF); d[s] = 0;
22
    using P = pair<long long,int>;
23
    priority_queue<P, vector<P>, greater<P>> pq; pq.push({0,s});
24
    while(!pq.empty()){
25
        auto [du,u] = pq.top(); pq.pop(); if (du != d[u]) continue;
26
        for (auto [v,w]: adj[u]) if (d[v] > du + w) { d[v] = du + w; pq.push({d[v], v}); }
27
    }
28
    return d;
29
}
30
31
int main(){
32
    // Build a small graph with negative edges but no negative cycles
33
    // 0->1 (-2), 0->2 (4), 1->2 (3), 1->3 (2), 2->3 (-1)
34
    int n = 4; vector<Edge> edges = {
35
        {0,1,-2}, {0,2,4}, {1,2,3}, {1,3,2}, {2,3,-1}
36
    };
37
38
    vector<long long> h;
39
    if (!bellman_ford_potentials(n, edges, h)) {
40
        cout << "NEGATIVE CYCLE\n"; return 0;
41
    }
42
43
    // Build reweighted graph
44
    vector<vector<pair<int,long long>>> adj(n);
45
    for (auto &e : edges) {
46
        long long wprime = e.w + h[e.u] - h[e.v];
47
        adj[e.u].push_back({e.v, wprime});
48
    }
49
50
    // Run Dijkstra from source s = 0 on reweighted graph
51
    int s = 0; auto dprime = dijkstra_reweighted(n, adj, s);
52
53
    // Convert back to original distances and print both
54
    cout << fixed;
55
    for (int v = 0; v < n; ++v) {
56
        if (dprime[v] >= INF/2) {
57
            cout << "v=" << v << ": unreachable\n";
58
        } else {
59
            long long d_orig = dprime[v] - h[s] + h[v];
60
            cout << "v=" << v << ": d'(reweighted)=" << dprime[v]
61
                 << ", d(original)=" << d_orig << "\n";
62
        }
63
    }
64
    return 0;
65
}
66

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Edge { int u, v; long long w; };
5
const long long INF = (1LL<<60);
6
7
bool bellman_ford_potentials(int n, const vector<Edge>& edges, vector<long long>& h) {
8
    h.assign(n, 0LL);
9
    for (int i = 0; i < n - 1; ++i) {
10
        bool changed = false;
11
        for (auto &e : edges) {
12
            if (h[e.v] > h[e.u] + e.w) { h[e.v] = h[e.u] + e.w; changed = true; }
13
        }
14
        if (!changed) break;
15
    }
16
    for (auto &e : edges) if (h[e.v] > h[e.u] + e.w) return false;
17
    return true;
18
}
19
20
vector<vector<long long>> floyd_warshall(int n, const vector<Edge>& edges) {
21
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
22
    for (int i = 0; i < n; ++i) dist[i][i] = 0;
23
    for (auto &e: edges) dist[e.u][e.v] = min(dist[e.u][e.v], e.w);
24
    for (int k = 0; k < n; ++k)
25
        for (int i = 0; i < n; ++i) if (dist[i][k] < INF/2)
26
            for (int j = 0; j < n; ++j) if (dist[k][j] < INF/2)
27
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
28
    return dist;
29
}
30
31
vector<vector<long long>> johnson(int n, const vector<Edge>& edges) {
32
    vector<long long> h;
33
    if (!bellman_ford_potentials(n, edges, h)) return {}; // empty => negative cycle
34
    vector<vector<pair<int,long long>>> adj(n);
35
    for (auto &e : edges) {
36
        long long wprime = e.w + h[e.u] - h[e.v];
37
        adj[e.u].push_back({e.v, wprime});
38
    }
39
    const long long INFLL = INF;
40
    vector<vector<long long>> ans(n, vector<long long>(n, INFLL));
41
    using P = pair<long long,int>;
42
    for (int s = 0; s < n; ++s) {
43
        vector<long long> d(n, INFLL); d[s] = 0;
44
        priority_queue<P, vector<P>, greater<P>> pq; pq.push({0, s});
45
        while(!pq.empty()) {
46
            auto [du,u] = pq.top(); pq.pop(); if (du != d[u]) continue;
47
            for (auto [v,w]: adj[u]) if (d[v] > du + w) { d[v] = du + w; pq.push({d[v], v}); }
48
        }
49
        for (int v = 0; v < n; ++v) if (d[v] < INFLL/2) ans[s][v] = d[v] - h[s] + h[v];
50
    }
51
    return ans;
52
}
53
54
int main(){
55
    ios::sync_with_stdio(false);
56
    cin.tie(nullptr);
57
58
    int n, m; cin >> n >> m;
59
    vector<Edge> edges(m);
60
    for (int i = 0; i < m; ++i) cin >> edges[i].u >> edges[i].v >> edges[i].w;
61
62
    // Heuristic: if m > n * (n / 8), treat as dense, else sparse.
63
    // Tune threshold empirically; here we pick 12.5% density as a demo cutoff.
64
    long long threshold = 1LL * n * max(1, n / 8);
65
    if ((long long)m > threshold) {
66
        auto dist = floyd_warshall(n, edges);
67
        // Output
68
        for (int i = 0; i < n; ++i) {
69
            for (int j = 0; j < n; ++j) {
70
                if (dist[i][j] >= INF/2) cout << "INF"; else cout << dist[i][j];
71
                if (j+1<n) cout << ' ';
72
            }
73
            cout << '\n';
74
        }
75
    } else {
76
        auto dist = johnson(n, edges);
77
        if (dist.empty()) { cout << "NEGATIVE CYCLE\n"; return 0; }
78
        for (int i = 0; i < n; ++i) {
79
            for (int j = 0; j < n; ++j) {
80
                if (dist[i][j] >= INF/2) cout << "INF"; else cout << dist[i][j];
81
                if (j+1<n) cout << ' ';
82
            }
83
            cout << '\n';
84
        }
85
    }
86
    return 0;
87
}
88