Detect Negative cycle in a graph

The problem, simply

You get a directed graph with V towns and E one-way roads. Each road has a cost, and some costs are negative, which means the road pays you.

A negative cycle is a loop of roads whose costs add up to less than zero. Return true if the graph has one anywhere, and false if it does not.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build a full table of the cheapest cost from every town to every town with Floyd-Warshall. Then look at the cost from each town back to itself. A fair map gives 0. A money loop gives less than 0.

1. Fill d[i][j] with the road cost, 0 on the diagonal, and infinity elsewhere.
2. For every middle town m, for every i and j, try going i to m to j.
3. If any d[i][i] < 0, return true.

class NegativeCycleFloyd {
    public static boolean hasNegativeCycle(int V, int[][] edges) {
        final long INF = Long.MAX_VALUE / 4;
        long[][] d = new long[V][V];
        for (long[] row : d) Arrays.fill(row, INF);
        for (int i = 0; i < V; i++) d[i][i] = 0;
        for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);

        for (int m = 0; m < V; m++)
            for (int i = 0; i < V; i++)
                for (int j = 0; j < V; j++)
                    if (d[i][m] < INF && d[m][j] < INF && d[i][m] + d[m][j] < d[i][j])
                        d[i][j] = d[i][m] + d[m][j];

        for (int i = 0; i < V; i++) if (d[i][i] < 0) return true;   // home costs less than 0
        return false;
    }
}

How long it takes: three loops over the towns, O(V^3). Extra room: the table, O(V^2). It is a fine choice for small dense maps, and it also tells you which towns sit on or behind a loop.

Way 2: the clever way

Bellman-Ford, started from every town at once.

1. Set every town's cost to 0. This is like adding a helper town with a free road to every town, so every loop can be reached.
2. Repeat V - 1 times: for every road u to v with cost w, if dist[u] + w < dist[v], set dist[v] = dist[u] + w.
3. Do one more pass over the roads. If any road can still lower a cost, return true. Otherwise return false.

class NegativeCycleBellmanFord {
    public static boolean hasNegativeCycle(int V, int[][] edges) {
        long[] dist = new long[V];                        // all 0: every loop is reachable
        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] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    changed = true;
                }
            }
            if (!changed) return false;                   // settled early, so no money loop
        }
        for (int[] e : edges) {
            if (dist[e[0]] + e[2] < dist[e[1]]) return true;   // still dropping
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1, 5}, {2, 3, 1}, {3, 4, -3}, {4, 2, 1}, {4, 1, 2}};
        System.out.println(hasNegativeCycle(5, edges));  // true
    }
}

How long it takes: V - 1 rounds over E roads, plus one check, O(V * E). Extra room: one cost array, O(V).

Watch out for

• With an infinity start, skip roads whose start town is still infinity, or INF + w overflows.
• Use long costs. Many rounds of negative roads can go below Integer.MIN_VALUE on big inputs.
• Doing V full rounds and then checking for change also works. Just make sure the check is a separate pass after V - 1 rounds.
• A loop with total exactly 0 is not negative. Use <, not <=.

What interviewers ask next

• How do you print the loop? Keep parent[v] = u on each improvement. Take the town x improved in the extra pass, step back through parent V times to be sure you are inside the loop, then follow parents until you return.
• Currency arbitrage: rates r multiply, so use cost -log(r). A loop whose rates multiply to more than 1 becomes a negative cycle.
• Can Dijkstra find it? No. Dijkstra assumes costs never go down along a path, which negative roads break.
• Which towns have no real cheapest cost? Any town reachable from a negative loop. Mark towns improved in an extra pass, then spread the mark along roads.
• Is there something faster in practice? SPFA, a queue-based Bellman-Ford, is often faster, but it is still O(V * E) in the worst case.

Remember this

Grown-up words: towns are vertices, toll roads are weighted directed edges, the money loop is a negative weight cycle, lowering a cost is relaxing an edge, the helper town with free roads is a virtual source, the rounds are Bellman-Ford, and the table of every pair is Floyd-Warshall.