Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. A shortest path without cycles uses at most n − 1 edges, so n − 1 rounds of relaxing every edge are enough.
  2. 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