Implement Bellman-Ford and Floyd-Warshall

negative edges and all-pairs paths

Challenge 6 of GraphsAdvanced~60 minFree

Shortest paths when edges can be negative. Build Bellman-Ford to relax edges from a single source, detect negative-weight cycles, combine both into one safe contract, then compute all-pairs distances with Floyd-Warshall. Edges are directed tuples (u, v, w) and unreachable pairs use float('inf').

5 steps

1. 1Bellman-Ford from a source
2. 2Detect a negative cycle
3. 3A safe Bellman-Ford contract
4. 4Floyd-Warshall all-pairs
5. 5Query the matrix