Intuition The one core ideaA graph is a map of places joined by roads that have costs, and Bellman-Ford finds the cheapest way from one starting place to every other place — even when some roads pay you (negative cost). It does this by patiently checking every road over and over, letting cheap news spread one road-hop further with each round — and if the cost of some city never stops dropping , that reveals a negative-cost loop .
Before you can read the parent note on Bellman-Ford, you must own every word and symbol it throws at you. This page builds each one from nothing, in an order where each idea leans only on the ones before it.
Definition Graph, vertex, edgeA graph is a set of dots called vertices (also "nodes"), joined by lines called edges . Each edge connects two vertices. That's the whole object — dots and connections.
Think of vertices as cities and edges as roads between them.
A single vertex is drawn as a dot. In code we usually name them by number: 0 , 1 , 2 , …
The letter V the number of vertices — how many dots. In the picture V = 4
The letter E the number of edges — how many roads. In the picture E = 4
Why the topic needs this: Bellman-Ford's whole running time is written O ( V ⋅ E ) V E
A directed edge is a one-way road. We write it u → v from u to v not back along the same edge. The arrow shows the allowed direction.
Here u v
Every edge carries a number called its weight , written w ( u , v ) u v cost to travel that road.
w ( 0 , 1 ) = 4 A negative weight like w ( 1 , 2 ) = − 3 pays you 3 — travelling it lowers your total cost. Look at the coral edge in the figure.
Intuition Why negatives matter at allIf every road cost money (all weights ≥ 0 longer route might end up cheaper . This single fact is why we need Bellman-Ford instead of the faster Dijkstra's Algorithm .
Definition How the edges are stored: a list of triplesWhen we say ==edges== we mean a list, one item per edge, where each item is a triple (u, v, w) — the start vertex, the end vertex, and the weight. For the picture above:
edges = [ ( 0 , 1 , 4 ) , ( 0 , 2 , 5 ) , ( 1 , 2 , − 3 ) , ( 2 , 3 , 2 ) ] (u, v, w) in edges" simply walks through every road one at a time , handing you its start, end, and cost. That is the only data Bellman-Ford ever reads.
A path is a sequence of vertices where each consecutive pair is joined by a directed edge, following the arrows. Example: 0 → 1 → 2
A path is simple if it never repeats a vertex . Since there are only V V V − 1
The figure shows one simple path (mint) using 3 vertices / 2 edges, and one non-simple path (coral, dashed) that loops back and repeats a vertex.
Intuition Why "at most V−1 edges" is the heart of the algorithmA chain touching every one of V V − 1 V V − 1 V − 1 V − 1
Definition Source and distanceThe source , written s src in code), is the one city we start from. The distance to a city v dist ( v ) cheapest total weight of any path from s v dist==, where dist[v] holds the best cost to v
If no path reaches v ∞
Why the topic needs this: Bellman-Ford is a single-source algorithm — everything is measured as a distance from one fixed s Shortest Path Problem .
Definition Infinity as "not yet reached"∞ placeholder meaning "no path found yet, so treat as impossibly large" . In code this is written float('inf'), which is just that language's spelling of ∞
Intuition Picture it as fogAt the start, every city except the source is hidden in fog: distance = ∞ ∞
Common mistake Adding to infinityIf dist[u] is still ∞ ∞ + w ∞ dist[u] is finite (not ∞
Everything Bellman-Ford does is built from a single tiny operation.
To relax the edge u → v w ask whether going through u v , and if so, update.
if dist [ u ] + w < dist [ v ] then dist [ v ] ← dist [ u ] + w
Read it in plain words: "If the cost to reach u u v v v
The figure shows one relaxation: before, v u ←
Intuition Why relaxing repeatedly is enoughOne relaxation lets good news travel exactly one road further . Do a full sweep over all E V − 1 Graph Relaxation and the Dynamic Programming view.
O ( ⋅ ) how the work grows as the input grows, ignoring constant factors. O ( V ⋅ E ) V E
Why this exact number? We do V − 1 V E ≈ ( V − 1 ) ⋅ E O ( V ⋅ E )
The parent note writes D [ k ] [ v ]
The base row (where the table starts): with 0 D [ 0 ] [ s ] = 0 , D [ 0 ] [ v ] = ∞ ( v = s ) . dist array from Section 4.
Because a simple path uses at most V − 1 k = V − 1
Intuition What if a loop of roads pays you every lap?Suppose roads 0 → 1 → 2 → 0 negative total. Then each time you drive the loop your cost drops — so you could loop forever and reach − ∞ no cheapest path any more. Such a loop is a negative-weight cycle , and detecting it is a headline feature of Bellman-Ford.
Definition How Bellman-Ford spots it (preview)After the V − 1 one extra sweep : if any edge can still be relaxed (some dist[v] still drops), the only possible cause is a negative-cost loop reachable from the source. You will meet the full argument in the parent note and in Negative Weight Cycles — for now, just know why it exists: negative loops make "shortest distance" undefined, so we must flag them.
Simple path uses V-1 edges
DP table D k v and recurrence
What is a vertex, and what does V A dot / place in the graph; V
What is a directed edge u → v A one-way road you can travel from u v
What does w ( u , v ) The weight (cost) of the edge from u v
What is edges as a data structure? A list of triples ( u , v , w )
What does a negative weight represent? A road that lowers your total cost — it pays you.
What is a simple path, and how many edges can it use? A path with no repeated vertex; at most V − 1
What is the source s The single starting vertex all distances are measured from.
How is the dist array initialised? dist [ s ] = 0 dist [ v ] = ∞ v = s
Why do we initialise unreached cities to ∞ They have no known path yet; ∞
State the relaxation rule in words. If dist [ u ] + w < dist [ v ] dist [ v ] = dist [ u ] + w
Why only relax when dist[u] is finite? You can't spread cost from a city you haven't reached; ∞ + w ∞
What does O ( V ⋅ E ) Work grows like V E
What does D [ k ] [ v ] Cheapest cost from s v k D [ k ] [ v ] = min ( D [ k − 1 ] [ v ] , min ( u , v ) D [ k − 1 ] [ u ] + w ( u , v ))
What is a negative-weight cycle, and how is it flagged? A loop whose weights sum below zero; flagged if one extra sweep after V − 1
Parent topic (Hinglish) Shortest Path Problem — the problem all of this solvesGraph Relaxation — the single move built hereDynamic Programming — the D [ k ] [ v ] Dijkstra's Algorithm — the faster cousin that needs non-negative weightsNegative Weight Cycles — what negative weights can createFloyd-Warshall — the all-pairs relativeSPFA — a queue-based speedup