Bellman-Ford

Shortest path with negative edge weights and negative cycle detection in O(V*E).

[Graph]|

Jul 9, 2026

|explanatory_notes.md|

#bellman-ford#shortest-path#negative-weights#negative-cycle

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;

struct Edge { int u, v; ll w; };

vector<Edge> edges;
vector<ll> dist;

void bellmanFord(int src, int n) {
    dist.assign(n + 1, INF);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++)
        for (auto &[u, v, w] : edges)
            if (dist[u] < INF)
                dist[v] = min(dist[v], dist[u] + w);
}

bool hasNegativeCycle() {
    for (auto &[u, v, w] : edges)
        if (dist[u] < INF && dist[v] > dist[u] + w)
            return true;
    return false;
}

26 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Bellman-Ford

Single-source shortest path supporting negative edge weights, plus negative cycle detection.

How It Works

Initialize

d[\text{src}] = 0

, all others

= \infty

Relax all edges

V - 1

times. Each round guarantees correctness for paths with one more edge

After

V - 1

rounds, run one more pass — if any distance still improves, a negative cycle exists

When to Use

Graphs with negative edge weights (Dijkstra fails here)

Negative cycle detection — currency exchange, arbitrage

Difference constraint systems (

x_j - x_i \le w

modeled as edge

i \to j

with weight

w

)

Complexity

Time —

O(V \cdot E)

Space —

O(V + E)