Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
Bellman–Ford computes shortest distances from a source through repeated edge relaxation and supports negative edge weights.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
Distances and edge weights must use the same additive unit; k and |V| are dimensionless counts.
| Symbol | Meaning | Unit |
|---|---|---|
| Best-known distance from source s to v using at most k edges | weight unit | |
| Weight of directed edge (u,v) | weight unit | |
| Set of directed graph edges | edges | |
| Maximum number of edges allowed in the current path | count | |
| Set of graph vertices | nodes |
d_k(v)=\min\left(d_{k-1}(v),\min_{(u,v)\in E}[d_{k-1}(u)+w(u,v)]\right)Set d0(s)=0 and d0(v)=∞ for every other vertex. Each round either keeps the previous path with at most k−1 edges or appends one incoming edge to such a path. After |V|−1 rounds, shortest distances are determined if no negative-weight cycle is reachable from s. A further relaxation that still improves a distance detects such a reachable cycle. With a straightforward edge scan, the running time is O(|V||E|); unreachable vertices remain at infinity. Edge weights may be negative, but shortest paths are not well-defined when a reachable negative cycle can be traversed repeatedly.
For directed weighted graphs; negative edges are allowed, but no negative cycle may be reachable from the source. After |V|−1 edge rounds, finite shortest distances are determined.
After k rounds, dynamic programming knows shortest paths using at most k edges.
Runtime with an edge scan
Each of at most |V| rounds scans all |E| edges; stopping when no value changes may save practical work.
Given s→a=4, s→b=5, a→b=−2, b→t=3 and a→t=4, find the shortest distance to t.
Through a, d(b)=4−2=2.
Through b, d(t)=2+3=5; the direct route through a costs 8.
Thus d(t)=5 via s→a→b→t.
Treating a negative edge as a negative cycle.
Individual negative edges are allowed; the problem is a negative-total-weight cycle reachable from s.
Formula cluster
Bellman–Ford handles negative edges; Dijkstra uses nonnegative weights for a faster greedy choice.
Dijkstra’s algorithm for weighted shortest paths
Graph search: BFS, DFS and shortest paths
Minimum spanning tree
Edges: s→a with 4, s→b with 5, a→b with −2, b→t with 3 and a→t with 4. Relaxing through a changes d(b) from 5 to 4−2=2; through b, d(t) becomes 2+3=5 rather than 8. Check: s→a→b→t costs 4−2+3=5, less than s→a→t at 8.
Find shortest paths in directed weighted graphs that may contain negative edges, and detect reachable negative-weight cycles.
Here is how to work through a typical Bellman–Ford algorithm for shortest paths (dk(v) = min(dk−1(v), dk−1(u)+w(u,v))) task step by step:
Task
Given s→a=4, s→b=5, a→b=−2, b→t=3 and a→t=4, find the shortest distance to t.
Solution path
Through a, d(b)=4−2=2.
Through b, d(t)=2+3=5; the direct route through a costs 8.
Thus d(t)=5 via s→a→b→t.
Bellman–Ford is appropriate when edge weights may be negative and you need shortest paths from a source. Dijkstra’s greedy step assumes nonnegative weights: once a vertex is finalized, a later negative detour must not improve it. Bellman–Ford instead relaxes every edge repeatedly and allows such improvements. With only nonnegative weights, Dijkstra is often faster. Both solve the same distance problem, but their assumptions and running times differ. Also check whether a reachable negative cycle exists. Check the input weights first, then inspect cycles reachable from the source.
A negative cycle has a total weight below zero along its directed edges. If it is reachable from the source and a destination can be reached afterward, the cycle can be repeated to make a path cheaper without bound. That destination then has no finite shortest path. A single negative edge does not cause this problem. After the usual |V|−1 rounds, Bellman–Ford checks whether another relaxation still improves a distance, detecting a reachable negative cycle. A negative cycle unreachable from the source does not affect this source’s paths.
If a shortest path exists and there is no reachable negative cycle, a shortest path can be chosen without repeated vertices. A simple path through at most |V| vertices has at most |V|−1 edges. In round k, the dynamic program accounts for paths with at most k edges. Thus |V|−1 rounds cover every simple shortest path. In an implementation that scans edges in place, improvements may propagate sooner depending on edge order, but the bound remains correct. This is an upper bound and can exceed the rounds actually needed.
The basic algorithm performs at most |V|−1 rounds and checks each of the |E| edges in every round. A check computes d(u)+w(u,v) and compares it with d(v), taking a constant number of operations. This gives O(|V||E|). One extra round for negative-cycle detection does not change the asymptotic bound. If a full round changes no distance, the algorithm can stop early. Actual runtime may therefore be better, but the standard guarantee for edge scanning is the product of vertex and edge counts.
For a directed edge u→v, compare the current d(v) with d(u)+w(u,v). If u is still unreachable, d(u)=∞, it yields no finite candidate. In the example, s→a costs four and a→b costs minus two, lowering d(b) from five to two. Edge b→t with weight three then sets d(t) to five. The resulting path s→a→b→t costs 4−2+3=5. Record each improvement and use consistent additive units for all edge weights. Keep each edge direction consistent throughout the calculation. Recheck all distances at the end.
Quanta exam set
Curated exam set for "Bellman–Ford algorithm for shortest paths":
Question (front)
Which formula describes Bellman–Ford algorithm for shortest paths?
Answer in your set
Question (front)
How do you rearrange Bellman–Ford algorithm for shortest paths for Runtime with an edge scan?
Answer in your set
Question (front)
Which common mistake happens with Bellman–Ford algorithm for shortest paths?
Answer in your set
+ 8 more cards: units, variables, derivation, example, exam task
The formula set contains 11 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for dk(v) = min(dk−1(v), dk−1(u)+w(u,v)): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential