Dijkstra's slower but braver cousin. It relaxes every edge V-1 times, so it handles negative weights and one extra pass tells you if a negative cycle exists.
A shortest path visits at most V-1 edges. Each full pass over all edges guarantees one more edge of every shortest path is locked in, so V-1 passes settle everything.
V-1 timesif dist[u]+w < dist[v] updatebool bellmanFord(int n, int src,
vector<array<int,3>>& edges, vector<int>& dist) {
dist.assign(n, INT_MAX);
dist[src] = 0;
// V-1 passes: each relaxes every edge once
for (int i = 1; i < n; i++)
for (auto& [u, v, w] : edges)
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w; // relax
// one more pass: any improvement = negative cycle
for (auto& [u, v, w] : edges)
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
return false; // negative cycle detected
return true; // dist[] holds shortest paths
}V-1 passes, each scanning all E edges. Slower than Dijkstra.
Just the distance array; edges can stay in an edge list.
And uniquely, detects negative-weight cycles.
dist[u] != INT_MAX before relaxing, or INT_MAX + w overflows.K+1 passes.