Bellman-Ford and Floyd-Warshall

Lesson 12 of 17 · Graphs and trees

Two shortest-path algorithms that also work with negative weights: Bellman-Ford finds the distances from one vertex and detects negative cycles, and Floyd-Warshall calculates the distances between all pairs of vertices in three nested loops.

Before you start: prerequisites – Dijkstra.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Bellman-Ford

A shortest path without cycles has at most n − 1 edges. That is why it is enough to go through all the edges n − 1 times and relax each one: after the k-th pass all the distances that are reached with at most k edges are correct.

If some distance decreases even in the n-th pass, there is a negative cycle reachable from the start – with it the path can be shortened infinitely.

#include <iostream>
#include <vector>
using namespace std;

const long long INF = 1e18;

struct Edge { int u, v, w; };

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> g(m);
    for (auto &e : g) cin >> e.u >> e.v >> e.w;   // directed edges u -> v
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;
    for (int pass = 1; pass <= n - 1; pass++)
        for (auto &e : g)
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
                dist[e.v] = dist[e.u] + e.w;
    // the n-th pass: if something still gets shorter, there is a negative cycle
    for (auto &e : g)
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            cout << "NEGATIVE CYCLE" << endl;
            return 0;
        }
    for (int v = 1; v <= n; v++) {
        if (dist[v] == INF) cout << "INF ";
        else cout << dist[v] << " ";
    }
    cout << endl;
    return 0;
}

Example 1

Input

4 5
1 2 4
1 3 5
2 3 -3
3 4 2
2 4 6

Output

0 4 1 3

Example 2 (a negative cycle 2 → 3 → 2)

Input

3 3
1 2 1
2 3 -2
3 2 1

Output

NEGATIVE CYCLE

The check dist[e.u] != INF is important: without it "∞ + a negative weight" would look like a shortening. The complexity is O(n · m) – slower than Dijkstra, but it works with negative edges.

Floyd-Warshall

At the beginning the matrix d[i][j] contains the weight of the edge i → j (or ∞, and d[i][i] = 0). Then for every vertex k we check whether the path i → k → j is shorter than the current i → j. After processing the vertex k the matrix contains the shortest paths that use only the vertices 1..k as intermediate vertices.

#include <iostream>
#include <algorithm>
using namespace std;

const long long INF = 1e18;
long long d[401][401];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = (i == j) ? 0 : INF;
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);          // there can be several edges between the same vertices
    }
    for (int k = 1; k <= n; k++)            // k must be the OUTER loop
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (d[i][k] != INF && d[k][j] != INF)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (d[i][j] == INF) cout << "INF";
            else cout << d[i][j];
            cout << (j < n ? " " : "\n");
        }
    }
    return 0;
}

Example

Input

4 4
1 2 3
2 3 -1
1 3 5
3 4 2

Output

0 3 2 4
INF 0 -1 1
INF INF 0 2
INF INF INF 0

Complexity O(n³) – for n ≤ 400–500. If after the algorithm some d[i][i] < 0, the vertex i is on a negative cycle.

Which algorithm to choose?

AlgorithmFrom whomNegative weightsComplexityWhen
BFSone vertex–O(n + m)all the edges have the same length
Dijkstraone vertexnoO((n + m) log n)the most common case
Bellman-Fordone vertexyes, detects negative cyclesO(n · m)negative edges, n·m ≤ ~108
Floyd-Warshallall pairsyesO(n³)a small graph, many queries
DP on a DAGone vertexyesO(n + m)a graph without cycles

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

Distances between towns

n ≤ 300 towns and m two-way roads with lengths are given, followed by q queries a b. For every query print the length of the shortest path, or -1 if there is no path.

Example

Input

4 3
1 2 5
2 3 2
1 3 9
3
1 3
3 1
1 4

Output

7
7
-1
TASK 02Difficulty: harder

Profit at an exchange office

An exchange office has n currencies and m rates of the form a b c: exchanging the currency a for b "costs" c points (c can be negative – then you gain). Is there a sequence of exchanges that starts and ends with the same currency and brings a profit in total (a sum smaller than 0)? Print YES or NO.

Example 1

Input

3 3
1 2 1
2 3 -2
3 1 0

Output

YES

Example 2

Input

3 3
1 2 1
2 3 -1
3 1 1

Output

NO
Common mistakes and tips
  • In Bellman-Ford do not relax edges from a vertex with dist = ∞.
  • In Floyd-Warshall the loop over k must be the outer one.
  • For n = 1000 Floyd-Warshall is 109 operations – too slow; then run Dijkstra from every vertex or read the task again.

Check your knowledge

Open the quiz

Bellman-Ford and Floyd-Warshall

1. How many passes through all the edges are enough for Bellman-Ford if there is no negative cycle?




2. How does Bellman-Ford detect a negative cycle?




3. What is the complexity of Floyd-Warshall?