1. V-1 rounds
A shortest path has at most V-1 edges, so V-1 relaxation passes suffice.
for (let i = 0; i < n - 1; i += 1)Typorithm · hard
Bellman-Ford
▷ Interactive algorithm labbellman-fordgraph-algorithmsrelaxationnegative-edgesnegative-cycle
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Bellman-Ford
Graph Algorithms
Relax every edge V-1 times to handle negative weights; one extra round detects negative cycles.
Bellman-Ford finds shortest paths even with negative edge weights, which Dijkstra cannot.
Since a shortest path has at most V-1 edges, V-1 full passes over all edges settle every distance.
If any edge can still be relaxed on a V-th pass, the graph has a negative-weight cycle.
Preparing algorithm lab…
01
Relax all edges V-1 times.
02
Handles negative edges.
03
Extra pass detects negative cycles.
function bellmanFord(edges, n, start) {
const dist = new Array(n).fill(Infinity);
dist[start] = 0;
for (let i = 0; i < n - 1; i += 1) {
for (const [from, to, weight] of edges) {
if (dist[from] + weight < dist[to]) {
dist[to] = dist[from] + weight;
}
}
}
for (const [from, to, weight] of edges) {
if (dist[from] + weight < dist[to]) {
return null;
}
}
return dist;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Relax every edge
Each pass tries to improve every edge, unlike Dijkstra's one node at a time.
if (dist[from] + weight < dist[to])3. Update
Record a shorter distance whenever one is found.
dist[to] = dist[from] + weight4. Negative cycle
A relaxation still possible after V-1 rounds means a negative cycle exists.
return nullA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.