Implement Bellman-Ford and Floyd-WarshallStep 2 of 5

Detect a negative cycle

12345

Step 2: Detect a negative cycle

If a graph contains a cycle whose total weight is negative, shortest distances are undefined: you can loop forever to drive the cost down. Bellman-Ford detects this with one extra pass.

Implement has_negative_cycle(n, edges). Return True if the graph contains any negative-weight cycle, otherwise False.

To catch a cycle anywhere in the graph (even one not reachable from vertex 0), start every distance at 0, as if a virtual source pointed at all vertices.

Algorithm:

  • Set dist = [0] * n.
  • Relax every edge n - 1 times, exactly like Step 1 but without an infinity guard (no distance is ever infinite here).
  • Do one more pass. If any edge can still be relaxed (dist[u] + w < dist[v]), a negative cycle exists, so return True. Otherwise return False.

bellman_ford from Step 1 is provided.

Hints
Starter code
def bellman_ford(n, edges, source):
    dist = [float('inf')] * n
    dist[source] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist


def has_negative_cycle(n, edges):
    """Return True if any negative-weight cycle exists, else False."""
    # TODO: relax from all-zero distances, then test one more pass.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step