Skip to content
Hello Python

Relax Signed Edges with Bellman-Ford

Practice ExerciseIntermediateMediumArrayGraphBellman-Ford

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement bellman_ford_distances(node_count, edges, source). Directed weights may be negative. Return [] for a reachable negative cycle; otherwise distances with -1 for unreachable nodes.

Starter code

def bellman_ford_distances(node_count, edges, source):
    pass
Test cases

negative-edge

{
  "args": [
    4,
    [
      [
        0,
        1,
        4
      ],
      [
        0,
        2,
        5
      ],
      [
        1,
        2,
        -3
      ],
      [
        2,
        3,
        2
      ]
    ],
    0
  ]
}

Expected: [0,4,1,3]

negative-cycle

{
  "args": [
    3,
    [
      [
        0,
        1,
        1
      ],
      [
        1,
        2,
        -2
      ],
      [
        2,
        1,
        -2
      ]
    ],
    0
  ]
}

Expected: []

Wizard outline
  1. Step 1: Seed the reachable source

    Represent the source as zero and all other nodes as unreachable. Signed edges still need one known starting distance.

  2. Step 2: Perform one relaxation pass

    Propagate improvements across the edge list once. One pass makes the signed-edge comparison observable.

  3. Step 3: Repeat until paths can span the graph

    Run up to node_count - 1 passes and stop early when unchanged. A simple shortest path uses at most node_count - 1 edges.

  4. Step 4: Reject a reachable negative cycle

    Use one extra scan to detect an improvement that should be impossible. Any improvement after node_count - 1 passes proves a reachable negative cycle.

Footguns and prerequisites
  • Relaxing from infinity invents unreachable paths.
  • Treating any negative cycle anywhere as reachable violates the source contract.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Relax every reachable directed edge for at most V-1 passes, then perform one proof pass for a negative cycle.

Why it works: Every simple shortest path has at most V-1 edges, so repeated relaxation discovers its cost. A further reachable improvement requires a repeated vertex and therefore a reachable negative cycle.

def bellman_ford_distances(node_count, edges, source):
    distances = [float('inf')] * node_count
    distances[source] = 0
    for _ in range(node_count - 1):
        changed = False
        for start, end, weight in edges:
            if distances[start] != float('inf') and distances[start] + weight < distances[end]:
                distances[end] = distances[start] + weight
                changed = True
        if not changed:
            break
    for start, end, weight in edges:
        if distances[start] != float('inf') and distances[start] + weight < distances[end]:
            return []
    return [-1 if value == float('inf') else value for value in distances]