Purpose
Finds the shortest distance from a specified starting point to the destination. Negative edges are supported. Negative cycles can be detected.
Time Complexity
Depends
Usage
Declaration
auto res = bellmanford(g, s, e);Get the shortest path from s to e using res.path.
Get the shortest distance from s to each vertex using res.distances. If no path exists, it returns INF.
Check if a negative cycle exists in g using res.hascycle.
Implementation
struct bellmanford_return { vector<int> path, distances; bool hascycle;};bellmanford_return bellmanford(DirectedGraph &_g,int s, int e) { vector<int> cnt(_g.g.size()), dist(_g.g.size(), INF), path, p(_g.g.size(), -1); vector<bool> inque(_g.g.size()); queue<int> q; dist[s] = 0; q.push(s); inque[s] = true; while (!q.empty()) { const int from = q.front(); q.pop(); inque[from] = false; for (const auto &edge : g[from]) { const int d = (dist[from] + edge.cost); if (d < dist[edge.to]) { dist[edge.to] = d; p[edge.to] = from; if (!inque[edge.to]) { q.push(edge.to); inque[edge.to] = true; ++cnt[edge.to]; if ((int)g.size() < cnt[edge.to]) return {vector<int>(), vector<int>(), true}; } } } } if (dist[e] != INF) { for (int i = e; i != -1; i = p[i]) path.push_back(i); reverse(path.begin(), path.end()); } return {path, dist, false};}