Workspace

Problem workspace

3 day streakD

Bellman–Ford Algorithm

MediumGraphsShortest paths

The challenge

Find shortest distances from a source when edges may have negative weights. Detect a negative cycle reachable from that source.

Edges are directed. A negative cycle in a disconnected, unreachable component does not invalidate this source’s distances.

Example

With B → C of weight −2: A:0, B:3, C:1, D:4, E:5, F:1. Adding D → B of weight −3 makes a reachable negative cycle.

Use the walkthrough below to inspect the input and each state change.

See Bellman–Ford, step by step

Follow the edges. Watch the state change.

Directed · 6 vertices · 7 edgesA = 0, B = 1, …
Negative edgeDirected graph with 6 vertices. Initialize the source at zero. Negative edges are allowed. A pass checks every directed edge in the listed order. The edge list and state table below provide the graph in text.412-2831ABCDEF
CurrentVisited / acceptedUnvisited
Best distance from source
ABCDEF
0∞∞∞∞∞
Step 01 / 12

Initialize the source at zero.

Negative edges are allowed. A pass checks every directed edge in the listed order.

distance[source] = 0
View input edges

A → B (4) · A → F (1) · F → B (2) · B → C (-2) · F → E (8) · C → D (3) · D → E (1)

Source: A. Adjacency entries follow this edge order.

Put it into code

Repeated relaxation works without greedily declaring any distance final.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

from math import inf

def bellman_ford(n, edges, source):
    # Directed edges: (u, v, weight).
    distance = [inf] * n
    distance[source] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, weight in edges:
            if distance[u] != inf and distance[u] + weight < distance[v]:
                distance[v] = distance[u] + weight
                changed = True
        if not changed:
            break

    for u, v, weight in edges:
        if distance[u] != inf and distance[u] + weight < distance[v]:
            return None  # Negative cycle reachable from source.
    return distance

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap