Implement Bellman-Ford and Floyd-WarshallStep 3 of 5

A safe Bellman-Ford contract

12345

Step 3: A safe Bellman-Ford contract

Real callers want both answers at once: the distances and whether they can be trusted. Combine Steps 1 and 2 into a single clear contract.

Implement bellman_ford_safe(n, edges, source). Return a tuple (dist, neg) where:

  • dist is the list of shortest distances from source (float('inf') for unreachable), exactly as in Step 1.
  • neg is a bool that is True when a relaxation is still possible after n - 1 passes, meaning a negative cycle affects these distances.

Algorithm:

  • Compute dist with the same n - 1 relaxation passes as Step 1 (keep the infinity guard).
  • Do one extra pass over the edges. If any edge with a finite dist[u] can still be relaxed, set neg = True and stop; otherwise neg stays False.
  • Return (dist, neg).

bellman_ford and has_negative_cycle from earlier steps are 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):
    dist = [0] * n
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True
    return False


def bellman_ford_safe(n, edges, source):
    """Return (dist, neg): distances from source and whether a negative cycle affects them."""
    # TODO: relax n - 1 times, then set neg from one extra 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