# Bellman–Ford Algorithm: C++ Implementation and Deep Dive ## Introduction The Bellman–Ford algorithm computes shortest paths from a single source in graphs that may contain negative edge weights. Unlike Dijkstra, Bellman–Ford handles negative weights and also detects negative-weight cycles reachable from the source — an important property for many applications (currency arbitrage detection, constraint satisfaction, etc.). This post walks through a practical C++ implementation (link to source below), explains the data structures and design choices, runs a worked example, highlights edge cases, and suggests improvements. --- ## When to use Bellman–Ford - When edges can have negative weights. - When you need to detect negative-weight cycles reachable from the source. - For correctness over raw speed — Bellman–Ford is O(V·E) and therefore slower than Dijkstra on non-negative graphs. --- ## Algorithm overview (high level) 1. Initialize distances from source to every vertex as +∞, and source distance = 0. 2. Relax every edge repeatedly for (V − 1) iterations (where V is number of vertices). 3. After step (2), distances are shortest paths if no negative cycles exist. 4. To detect negative cycles: do one more pass; if any distance can still be reduced, a negative-weight cycle exists. Complexity: O(V · E) time, O(V + E) memory for a typical adjacency list representation. --- ## Source code (reference) The implementation used in this article is available on GitHub: https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Bellman.cpp. The code represents the graph as an adjacency list vector<vector<pair<ll,ll>>> adj; where adj[u] holds pairs (v, w) for outgoing edges. A pth vector stores a {cost, predecessor} pair for each node so we can print distances (and reconstruct paths with an extra step). Key functions in the implementation: - Bellman(adj, pth) — performs (V−1) relaxation rounds over all edges. - detect_neg(adj, pth) — checks whether another relaxation is still possible (negative cycle). ### Important implementation notes - Distances are stored in pth[i][0].first (initialized to INT_MAX for unreachable nodes), and the predecessor is pth[i][0].second. - pth[0][0].first = 0 — the implementation assumes node 0 is the source. - The relaxation loops iterate over adjacency lists and update pth[v] when dist[u] + weight(u,v) is smaller. --- ## Example: step-by-step (from the sample in the repository) Input (n = 5, e = 10): 1 2 5 1 3 8 1 4 -4 2 1 -2 3 2 -3 3 4 9 4 0 2 4 2 7 0 1 6 0 3 7 This code sets source = 0. After running Bellman–Ford the computed distances from source 0 (indexing nodes 0..4) are: - node 0: 0 - node 1: 2 - node 2: 4 - node 3: 7 - node 4: -2 No negative cycle is reachable from the source in this example, so the detect_neg check returns false. The sample implementation prints pth[3][0].first, so the example output is: 7 (And it does not print yes for negative cycle because none was detected.) --- ## Code walkthrough & rationale - Graph representation: vector<vector<pair<ll,ll>>> adj gives fast iteration over outgoing edges; pair stores (dest, weight). - Distance + predecessor: pth stores {distance, predecessor} so the algorithm can both compute distances and later reconstruct paths if desired. - Relaxation loop: the implementation performs V-1 full passes where each pass iterates every adjacency list and applies the relaxation rule. - Negative cycle detection: a final pass checks if any distance can be reduced; any such reduction implies a negative-weight cycle is reachable. ### Why V-1 iterations? A shortest simple path contains at most V-1 edges. After relaxing all edges V-1 times, all shortest path distances (that don't go through negative cycles) will have been found. --- ## Edge cases & improvements 1. Large INF sentinel: using INT_MAX can cause integer overflow when adding weights. Prefer long long with LLONG_MAX/2 as INF and check overflow-safe conditions (if (dist[u] != INF && dist[u] + w < dist[v])). 2. Edge-list representation: iterating over all edges (as a flat list) is typically simpler and avoids nested loops over i and adjacency lists. Example: for (auto &e: edges) relax(e.u, e.v, e.w);. 3. Path reconstruction: store predecessors; after relaxations, reconstruct path from dest back to source by following predecessors (careful with unreachable nodes/INT_MAX). 4. Performance: Bellman–Ford is O(VE); if all weights are non-negative Dijkstra is much faster. Use SPFA (queue-based) only with understanding of worst-case behavior. 5. Robust IO & validation: the repository code assumes proper 0-based node indexing and valid edge count — add input validation in production code. --- ## When Bellman–Ford fails / caveats - If there is a negative-weight cycle reachable from the source, shortest paths are undefined (distances can be arbitrarily small). The algorithm can still detect the presence of such cycles, which is often what you need. --- ## Testing suggestions - Test graphs with positive, zero, and negative weights. - Test graphs that contain a negative cycle reachable from the source — confirm detect_neg returns true. - Compare results with a known-good Bellman–Ford implementation. --- ## Summary Bellman–Ford is the go-to algorithm for single-source shortest-path problems with possible negative weights and for negative-cycle detection. The C++ implementation in the linked repository is concise and follows the classical relaxation scheme — with a couple of practical improvements recommended above (use long long, safer INF, and path reconstruction). --- Repository: https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Bellman.cpp Images (use in article): 1. https://www.shutterstock.com/image-photo/programmer-cyber-security-technology-male-600nw-2464110045.jpg 2. https://www.snexplores.org/wp-content/uploads/2020/11/1030_algorithm_explainer-1028x579.jpg 3. https://i0.wp.com/bdtechtalks.com/wp-content/uploads/2022/02/algorithm-formulation.jpg?ssl=1