Bellman-Ford shortest path

Shortest distance from one source to every node, even with negative edge weights (as long as there is no negative cycle).

The idea

Relax every edge, up to V - 1 times: if going through edge (u, v) beats the current best distance to v, update it. Because the shortest path between any two nodes uses at most V - 1 edges, V - 1 full passes are always enough to reach every distance, even with some negative weights.

Code

public static Dictionary<char, int> BellmanFord(
        List<(char u, char v, int w)> edges, char src, int vertexCount) {
    var dist = new Dictionary<char, int>();
    dist[src] = 0;
    for (int i = 0; i < vertexCount - 1; i++) {
        bool changed = false;
        foreach (var (u, v, w) in edges) {
            if (dist.GetValueOrDefault(u, int.MaxValue) != int.MaxValue
                    && dist[u] + w < dist.GetValueOrDefault(v, int.MaxValue)) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) break; // nothing improved, distances are already final
    }
    foreach (var (u, v, w) in edges) // one more pass: if anything still improves, there is a negative cycle
        if (dist[u] + w < dist.GetValueOrDefault(v, int.MaxValue)) throw new Exception("negative cycle");
    return dist;
}

Tips

• It handles negative edges that break Dijkstra, at the cost of O(V × E) instead of O(E log V).
• If any edge still relaxes after V - 1 passes, the graph has a negative cycle and "shortest path" is not even well defined.

In the .NET library

Dijkstra finalises a node's distance the moment it is dequeued, which only works because it always picks the current closest node; a negative edge can undercut an already-finalised distance later, which is exactly what Bellman-Ford guards against by revisiting every edge repeatedly.