Bellman–Ford, Floyd–Warshall and Johnson

Bellman–Ford relaxes every edge for V−1 rounds. After k rounds it covers best walks with at most k edges. An improvement on roundV reveals a source-reachable negative cycle; unreachable negative cycles do not affect that source.

Floyd–Warshall is all-pairs DP with dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]). k must be outermost to preserve the permitted-intermediate-vertices invariant. Initialise diagonal0 and minimum parallel-edge costs. Negative diagonal values signal negative cycles; affected pairs have no finite optimum.

Johnson uses Bellman–Ford potentials to reweight edges nonnegatively, then runs Dijkstra from each source. Convert distances back afterward. Negative cycles must cause failure rather than fabricated finite answers.

def bellman_ford(vertices, edges, source):
    d = {v: float("inf") for v in vertices}; d[source] = 0
    for _ in range(len(vertices)-1):
        changed = False
        for u,v,w in edges:
            if d[u] != float("inf") and d[u]+w < d[v]:
                d[v] = d[u]+w; changed = True
        if not changed: break
    if any(d[u] != float("inf") and d[u]+w < d[v] for u,v,w in edges):
        raise ValueError("reachable negative cycle")
    return d
assert bellman_ford("ABC",[("A","B",4),("A","C",5),("B","C",-2)],"A")["C"] == 2