# Bellman–Ford Algorithm — Single-Source Shortest Paths (C++) ## Introduction Bellman–Ford computes shortest paths from a single source in graphs that may contain negative edge weights. Unlike Dijkstra, it also detects negative-weight cycles reachable from the source. ## How it works (high level) - Initialize distances to `+∞`, distance[source] = 0. - Relax every edge `V-1` times (where `V` is number of vertices). Each relaxation attempts to improve the best-known distance. - After `V-1` iterations, perform a final pass: if any distance can still be relaxed, a negative cycle exists. ## Time & Space Complexity - Time: **O(V·E)** (V vertices, E edges) - Space: **O(V + E)** ## When to use - Use when graph may have negative edge weights but **no negative cycles**. Use it when detection of negative cycles is required. ## Key points in the reference implementation The project file: `Bellman.cpp` — full source: `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Bellman.cpp` ### Minimal code sketch ```cpp // Distances stored in pth[*][0].first; edges in adj[u]={ {v,w}, ... } void Bellman(vector<vector<pair<ll,ll>>>& adj, vector<vector<pair<ll,ll>>>& pth) { int s = adj.size()-1; while (s--) { for (int u = 0; u < adj.size(); ++u) { for (auto &e : adj[u]) { if (pth[e.first][0].first > pth[u][0].first + e.second) { pth[e.first][0] = { pth[u][0].first + e.second, u }; } } } } } ``` ## Example input (from repo) ``` 5 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 ``` ## Practical tips & pitfalls - Make sure to use a large sentinel (`INT_MAX` or `LLONG_MAX`) and check overflow before additions. - Watch indexing (0-based vs 1-based) in input. ## Further reading / Source Full source: `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/Bellman.cpp`.