Shortest Paths: Bellman-Ford — cheat sheet — Algorithms & Data Structures with Python

Bellman-Ford finds single-source shortest paths and, unlike Dijkstra, works when some edge weights are negative and can flag when no answer exists.

Core idea

Single-source shortest paths: from one source vertex, find the cheapest total edge weight to every other vertex.
Works with negative edge weights (a leg that earns money, releases energy, etc.).
dist[] holds the best distance known so far per vertex. Start: source = 0, all others = infinity.

To relax edge u -> v of weight w: if dist[u] + w < dist[v], set dist[v] = dist[u] + w.
Never makes a distance worse; only ever lowers it.

if dist[u] != INF and dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Relax every edge, V - 1 times.
Why V - 1: a shortest path (no negative cycle) visits each vertex at most once, so it has at most V - 1 edges. Each full round pushes correct answers one edge farther from the source, regardless of edge order.
Keep the guard dist[u] != INF so an unreached vertex offers nothing (matters if “infinity” is a large int rather than float("inf")).

Negative cycle: a loop whose weights sum to a negative number. If reachable from the source, there is no answer (distances fall toward negative infinity).
Detect: run one extra round after the V - 1. If any edge still relaxes, a negative cycle exists. Return None.
An undirected edge of weight -2 is two directed edges summing to -4, so any negative undirected edge is automatically a negative cycle.

Time O(V*E): V - 1 rounds times E edges each. The extra pass adds one more E, negligible.
Space O(V): just the dist list; edges are given, not copied.

	Bellman-Ford	Dijkstra
Negative edges	yes	no
Detects negative cycles	yes	no
Time	`O(V*E)`	`O((V + E) log V)`
Use when	some weights negative, or need cycle check	all weights non-negative, want speed

Running only one pass: settles only vertices one edge out; you must repeat V - 1 times.
Forgetting the extra pass: silently returns nonsense on a graph with a negative cycle.
Confusing V - 1 with E - 1: rounds scale with vertices, not edges.
A negative cycle the source cannot reach is not detected and does not affect these paths.