Practice › Graphs
Bellman-Ford Shortest Paths
Medium · Graphs · Asked at Amazon, Google, Microsoft
The graph is directed and weights may be negative. Print the shortest distance from node 1 to every node 1..n (INF if a node is unreachable). If a negative cycle is reachable from node 1, print only NEGATIVE CYCLE.
Input
First line: n m. Next m lines: u v w — an edge from u to v with weight w.
Output
n space-separated distances, or NEGATIVE CYCLE.
Constraints
- 1 ≤ n ≤ 500
- 0 ≤ m ≤ 5000
- -10^4 ≤ w ≤ 10^4
Relax every edge n − 1 times. If an edge can still be relaxed in an n-th round (from a reachable node), a negative cycle exists.
Example 1
Input
5 10 1 2 6 1 3 7 2 3 8 2 4 5 2 5 -4 3 4 -3 3 5 9 4 2 -2 5 1 2 5 4 7
Output
0 2 7 4 -2
Example 2
Input
3 3 1 2 1 2 3 -2 3 2 1
Output
NEGATIVE CYCLE
Hints
- A shortest path without cycles uses at most n − 1 edges, so n − 1 rounds of relaxing every edge are enough.
- If any edge from a reachable node can still be relaxed after that, a reachable negative cycle exists.
Approach
dist[1] = 0, all others ∞. Repeat n − 1 times: for every edge (u, v, w) with dist[u] finite, set dist[v] = min(dist[v], dist[u] + w). Then do one more pass; if anything still improves, report NEGATIVE CYCLE. Skipping unreachable u matters: a negative cycle that node 1 cannot reach must not affect the answer.
Complexity: O(n · m) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<array<long long, 3>> e(m);
for (auto &x : e) cin >> x[0] >> x[1] >> x[2];
const long long INF = LLONG_MAX / 4;
vector<long long> d(n + 1, INF);
d[1] = 0;
for (int i = 0; i < n - 1; i++)
for (auto &x : e)
if (d[x[0]] != INF && d[x[0]] + x[2] < d[x[1]]) d[x[1]] = d[x[0]] + x[2];
for (auto &x : e)
if (d[x[0]] != INF && d[x[0]] + x[2] < d[x[1]]) {
cout << "NEGATIVE CYCLE\n";
return 0;
}
for (int v = 1; v <= n; v++) {
if (d[v] == INF) cout << "INF";
else cout << d[v];
cout << (v < n ? " " : "\n");
}
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
e = [(data[2 + 3 * i], data[3 + 3 * i], data[4 + 3 * i]) for i in range(m)]
INF = float("inf")
d = [INF] * (n + 1)
d[1] = 0
for _ in range(n - 1):
changed = False
for u, v, w in e:
if d[u] != INF and d[u] + w < d[v]:
d[v] = d[u] + w
changed = True
if not changed:
break
if any(d[u] != INF and d[u] + w < d[v] for u, v, w in e):
print("NEGATIVE CYCLE")
else:
print(*["INF" if x == INF else x for x in d[1:]])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
long[][] e = new long[m][3];
for (int i = 0; i < m; i++) for (int j = 0; j < 3; j++) e[i][j] = sc.nextLong();
long INF = Long.MAX_VALUE / 4;
long[] d = new long[n + 1];
Arrays.fill(d, INF);
d[1] = 0;
for (int i = 0; i < n - 1; i++)
for (long[] x : e) {
int u = (int) x[0], v = (int) x[1];
if (d[u] != INF && d[u] + x[2] < d[v]) d[v] = d[u] + x[2];
}
for (long[] x : e) {
int u = (int) x[0], v = (int) x[1];
if (d[u] != INF && d[u] + x[2] < d[v]) {
System.out.println("NEGATIVE CYCLE");
return;
}
}
StringBuilder sb = new StringBuilder();
for (int v = 1; v <= n; v++) sb.append(d[v] == INF ? "INF" : String.valueOf(d[v])).append(v < n ? " " : "");
System.out.println(sb);
}
}Solve Bellman-Ford Shortest Paths online · All practice problems