Implement Bellman Ford Algorithm

The problem, simply

You get V stops and one-way roads between them. Every road has a price. Some prices are negative: taking that road gives you money back. You start at stop src.

For every stop, find the cheapest total price to get there from src. A stop you cannot reach costs infinity. If there is a loop of roads whose prices add up to less than zero, you could drive around it forever and get richer each time, so no cheapest price exists. Report that instead.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every route. From the source, walk every road to a stop you are not already on, and keep going. Each time you arrive somewhere, compare the price you paid with the best price written there.

1. Start at src with price 0.
2. At a stop, write down the price if it is the best so far.
3. Walk every road to a stop that is not already on your current route, adding its price.
4. When you return, take the stop off your route so other routes may use it.

import java.util.*;

class Solution {
    static final int INF = Integer.MAX_VALUE;

    public int[] cheapest(int V, int[][] edges, int src) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]});
        int[] best = new int[V];
        Arrays.fill(best, INF);
        walk(adj, src, 0, new boolean[V], best);
        return best;
    }

    private void walk(List<List<int[]>> adj, int u, int paid, boolean[] onRoute, int[] best) {
        best[u] = Math.min(best[u], paid);
        onRoute[u] = true;
        for (int[] road : adj.get(u)) {
            if (!onRoute[road[0]]) walk(adj, road[0], paid + road[1], onRoute, best);
        }
        onRoute[u] = false;                 // let other routes pass through u
    }
}

How long it takes: the number of routes that never repeat a stop can be about V!, so O(V!). Extra room: the route and the recursion, O(V). It also cannot tell you about a loop that pays you, because it never walks a loop.

Way 2: the clever way

Fix the sticky notes in rounds. Checking one road and fixing the note at its end is called relaxing the road.

1. Set dist[src] = 0 and every other dist to infinity.
2. Repeat V - 1 times: go through every road u > v with price w. If dist[u] is known and dist[u] + w < dist[v], set dist[v] = dist[u] + w.
3. If a whole round changes nothing, stop early.
4. Do one more round. If any road can still make a note cheaper, there is a negative loop.

Why V - 1 rounds? After round 1, every stop whose best route uses 1 road has its final price. After round 2, every stop whose best route uses 2 roads, and so on. A best route visits at most V stops, so it has at most V - 1 roads.

import java.util.*;

class Solution {
    static final int INF = Integer.MAX_VALUE;

    // returns null when there is a loop that pays you
    public int[] bellmanFord(int V, int[][] edges, int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int round = 1; round <= V - 1; round++) {
            boolean changed = false;
            for (int[] e : edges) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] != INF && dist[u] + w < dist[v]) {   // relax the road
                    dist[v] = dist[u] + w;
                    changed = true;
                }
            }
            if (!changed) break;            // nothing moved, so nothing will
        }
        for (int[] e : edges) {             // one extra round to catch a money loop
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INF && dist[u] + w < dist[v]) return null;
        }
        return dist;
    }
}

How long it takes: up to V - 1 rounds, each checking all E roads, O(V * E). Extra room: the dist array, O(V).

Watch out for

• Running Dijkstra on negative roads. Dijkstra locks a stop the first time it pops from the heap, and a later negative road can make it cheaper. Bellman Ford never locks anything.
• Skipping the extra round. Without it, a negative loop quietly gives wrong prices.
• Undirected graphs with a negative edge. A two-way road with price -2 is already a loop of -4, so Bellman Ford will report a negative cycle.
• The order of roads changes how many rounds you need, but not the final answer. In the animation, the edge list order let round 1 finish everything.

What interviewers ask next

• Cheapest flight with at most k stops (LeetCode 787)? Run exactly k + 1 rounds, and in each round read prices from a copy of the previous round, so one round adds at most one road.
• Which stops are hurt by a negative loop? After the extra round, every stop reachable from a road that still relaxes has price minus infinity. Mark them with a search from those stops.
• Can you speed it up? The queue version (SPFA) only rechecks roads leaving stops whose price just changed. It is often fast but still O(V * E) in the worst case.
• Bellman Ford or Dijkstra? With no negative roads, Dijkstra is faster at O(E log V). With negative roads, or when you must detect a negative loop, use Bellman Ford.
• Currency exchange: can you make money trading in a circle? Use price -log(rate) on each road. A circle of trades that makes money is a negative loop.

Remember this

Grown-up words: stops are vertices, roads are directed weighted edges, the sticky notes are the distance array, fixing a note is relaxation, the loop that pays you is a negative weight cycle, and the method is the Bellman Ford algorithm, a single source shortest path algorithm.