Log inSign up
mediumGeeksforGeeksNot Started

Bellman Ford Algorithm

Given a weighted, directed and connected graph of V vertices and list of edges where edges[i] = [u, v, w]. Find the shortest distance of all vertices from the source vertex S. If a negative weight cycle exists, detect and flag it.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given an integer V representing the number of vertices in a directed weighted graph, a list of edges where each edge is represented as [u, v, w] (meaning a directed edge from u to v with weight w), and a source vertex src.

Compute the shortest distance from src to all other vertices. If the graph contains a negative weight cycle reachable from src, indicate that by returning [-1] (or setting the cycle flag).

Vertices are numbered from 0 to V - 1. If a vertex is unreachable from src, its distance should be 10^8 (or infinity).

---

### Examples

Example 1: ``text Input: V = 4, edges = [[0, 1, 4], [0, 2, 5], [1, 2, -3], [2, 3, 2]], src = 0 Output: [0, 4, 1, 3] Explanation: - Distance to 0 = 0 - Distance to 1 = 4 (via 0 -> 1) - Distance to 2 = 0 -> 1 -> 2 (4 + (-3) = 1), which is shorter than 0 -> 2 (5) - Distance to 3 = 1 + 2 = 3 (via 0 -> 1 -> 2 -> 3) No negative cycle exists.

Example 2 (Negative Cycle): ``text Input: V = 3, edges = [[0, 1, 1], [1, 2, -2], [2, 0, -1]], src = 0 Output: [-1] Explanation: Cycle 0 -> 1 -> 2 -> 0 has total weight 1 + (-2) + (-1) = -2 < 0. Traversing this cycle continuously reduces path length infinitely.

---

### Constraints - 1 <= V <= 1000 - 0 <= edges.length <= 10000 - -1000 <= w <= 1000 - 0 <= u, v, src < V

Constraints:

  • 1 <= V <= 1000
  • 0 <= edges.length <= 10000
  • -1000 <= w <= 1000
  • 0 <= u, v, src < V

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why Dijkstra fails on graphs with negative edge weights.
  • Master the principle of edge relaxation over V - 1 iterations.
  • Detect negative weight cycles by executing a V-th relaxation pass.
  • Implement robust solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Single-source shortest path with negative edge weights.
  • Requirement to detect negative weight cycles.
  • Currency arbitrage or exchange-rate path optimization problems.

Algorithmic Decision Tree:

  • If all edge weights >= 0 -> Dijkstra is faster: O((V + E) log V).
  • If any edge weight < 0 -> Dijkstra fails; MUST use Bellman-Ford: O(V * E).
  • If all pairs shortest path is needed -> Floyd-Warshall: O(V3).

Connected Patterns:

Dijkstra's AlgorithmFloyd-Warshall AlgorithmShortest Path Faster Algorithm (SPFA)

1. All Simple Paths Enumeration (DFS Backtracking)

Intuition

Enumerate all possible simple paths from source to each vertex using backtracking and record minimum path lengths.

Algorithm

  1. Start DFS at source vertex src with current distance = 0.
  2. Mark current vertex as visited to prevent simple cycle re-entry.
  3. For each outgoing edge to an unvisited neighbor, recurse with updated distance.
  4. Backtrack by unmarking visited to explore alternative paths.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7const int INF = 1e8;
8
9void dfs(int u, int currentDist, const vector<vector<pair<int, int>>>& adj, vector<bool>& visited, vector<int>& minDist) {
10 minDist[u] = min(minDist[u], currentDist);
11 visited[u] = true;
12 for (const auto& edge : adj[u]) {
13 int v = edge.first;
14 int w = edge.second;
15 if (!visited[v]) {
16 dfs(v, currentDist + w, adj, visited, minDist);
17 }
18 }
19 visited[u] = false;
20}
21
22int main() {
23 int V = 4;
24 vector<vector<int>> edges = {{0, 1, 4}, {0, 2, 5}, {1, 2, -3}, {2, 3, 2}};
25 int src = 0;
26
27 vector<vector<pair<int, int>>> adj(V);
28 for (const auto& e : edges) {
29 adj[e[0]].push_back({e[1], e[2]});
30 }
31
32 vector<int> minDist(V, INF);
33 vector<bool> visited(V, false);
34 dfs(src, 0, adj, visited, minDist);
35
36 cout << "Shortest distances: ";
37 for (int d : minDist) cout << d << " ";
38 cout << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(V!)
  • Space complexity: O(V)

2. Dijkstra's Algorithm (Fast for Positive Weights)

Intuition

Use a min-heap priority queue to greedily expand the closest vertex. Fast on non-negative graphs but can loop or produce wrong distances on negative edges.

Algorithm

  1. Initialize distance array with INF, set dist[src] = 0.
  2. Push (0, src) into a priority queue.
  3. Pop the minimum distance vertex u.
  4. Relax all neighbors: if dist[u] + w < dist[v], update dist[v] and push (dist[v], v).
  5. Note: If graph contains negative weights, this approach is fundamentally flawed.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5using namespace std;
6
7const int INF = 1e8;
8
9vector<int> dijkstra(int V, const vector<vector<int>>& edges, int src) {
10 vector<vector<pair<int, int>>> adj(V);
11 for (const auto& e : edges) {
12 adj[e[0]].push_back({e[1], e[2]});
13 }
14
15 vector<int> dist(V, INF);
16 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
17
18 dist[src] = 0;
19 pq.push({0, src});
20
21 while (!pq.empty()) {
22 auto [d, u] = pq.top();
23 pq.pop();
24
25 if (d > dist[u]) continue;
26
27 for (auto& edge : adj[u]) {
28 int v = edge.first, w = edge.second;
29 if (dist[u] + w < dist[v]) {
30 dist[v] = dist[u] + w;
31 pq.push({dist[v], v});
32 }
33 }
34 }
35 return dist;
36}
37
38int main() {
39 int V = 4;
40 vector<vector<int>> edges = {{0, 1, 4}, {0, 2, 5}, {1, 2, -3}, {2, 3, 2}};
41 auto res = dijkstra(V, edges, 0);
42 cout << "Dijkstra result: ";
43 for (int d : res) cout << d << " ";
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(E log V)
  • Space complexity: O(V + E)

3. Bellman-Ford Algorithm with Early Stop & Negative Cycle Detection

Intuition

Relax all E edges V - 1 times. If any edge can still be relaxed on pass V, a negative cycle is detected and [-1] is returned.

Algorithm

  1. Initialize distance array dist with INF = 1e8, and set dist[src] = 0.
  2. Run an outer loop for i from 1 to V - 1:
  3. Maintain a flag updated = false.
  4. For every edge [u, v, w] in edges:
  5. If dist[u] != INF and dist[u] + w < dist[v]:
  6. Set dist[v] = dist[u] + w and updated = true.
  7. If updated == false, break early (shortest paths converged).
  8. Run a V-th iteration across all edges:
  9. If any edge satisfies dist[u] != INF and dist[u] + w < dist[v]:
  10. Return [-1] indicating a negative cycle.
  11. Return the dist array.

Bellman-Ford Step-by-Step Relaxation

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Init dist = [0, INF, INF, INF]
Visual state
Values and pointers at this exact step
table
This state table trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Start pass 1
Why this step matters

Init dist = [0, INF, INF, INF].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6const int INF = 1e8;
7
8vector<int> bellmanFord(int V, const vector<vector<int>>& edges, int src) {
9 vector<int> dist(V, INF);
10 dist[src] = 0;
11
12 // V - 1 relaxation iterations
13 for (int i = 0; i < V - 1; ++i) {
14 bool updated = false;
15 for (const auto& edge : edges) {
16 int u = edge[0], v = edge[1], w = edge[2];
17 if (dist[u] != INF && dist[u] + w < dist[v]) {
18 dist[v] = dist[u] + w;
19 updated = true;
20 }
21 }
22 if (!updated) break; // Early termination
23 }
24
25 // V-th iteration to detect negative cycle
26 for (const auto& edge : edges) {
27 int u = edge[0], v = edge[1], w = edge[2];
28 if (dist[u] != INF && dist[u] + w < dist[v]) {
29 return {-1}; // Negative cycle detected
30 }
31 }
32
33 return dist;
34}
35
36int main() {
37 int V = 4;
38 vector<vector<int>> edges = {{0, 1, 4}, {0, 2, 5}, {1, 2, -3}, {2, 3, 2}};
39 int src = 0;
40
41 vector<int> result = bellmanFord(V, edges, src);
42 cout << "Bellman-Ford Distances: ";
43 for (int d : result) cout << d << " ";
44 cout << endl;
45
46 // Test negative cycle
47 vector<vector<int>> cycleEdges = {{0, 1, 1}, {1, 2, -2}, {2, 0, -1}};
48 vector<int> cycleRes = bellmanFord(3, cycleEdges, 0);
49 cout << "Negative Cycle Result: " << cycleRes[0] << endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(V * E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All-Permutations DFS / Path EnumerationO(V!)O(V)Enumerate all simple paths from src to every destination.Combinatorial explosion of paths.
2.Dijkstra with Visited Cutoff (Incorrect for Negatives)O(E log V)O(V)Greedy priority queue extraction.Irrevocable node finalization assumption.
3.Bellman-Ford Algorithm (V-1 Relaxations + Cycle Check)OptimalO(V * E)O(V)Systematically propagate shortest path lengths up to k edges over k iterations.Iterating through all E edges V - 1 times.

Common Pitfalls & Crucial Edge Cases

Relaxing edges from unreachable vertices

Checking dist[u] + w < dist[v] when dist[u] is still infinity causes underflow or false propagation.

Failing to terminate early

If no distance changes during an entire iteration pass, the algorithm can break early, saving significant time.

Using Dijkstra on negative edge graphs

Dijkstra gives incorrect answers when negative edges exist.

Crucial Edge Cases to Validate:

  • Disconnected vertices — Initialized to infinity (1e8) and must not be relaxed if dist[u] == infinity.
  • Negative cycle unreachable from source — Will not be detected if only reachable nodes are relaxed, which is correct for single-source queries.
  • Graph with 1 vertex and 0 edges — Output is [0].
  • Self-loop with negative weight — Detected immediately on pass 1 or 2 as a negative cycle.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always mention early exit optimization: if an entire pass makes 0 updates, break out early.
  2. Explain the distinction between SPFA (queue-based Bellman-Ford) and standard Bellman-Ford.
  3. Highlight the currency exchange rate application (taking -log of rates transforms arbitrage into negative cycle detection).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Bellman-Ford perform exactly V - 1 relaxation iterations before checking for cycles?

2.What does it mean if an edge (u, v) with weight w can still be relaxed (dist[u] + w < dist[v]) on the V-th iteration?

Back to DSA Sheet