Graph Theory37 sections · 1633 units
Open in Course

Floyd-Warshall vs Bellman-Ford

(Two ways to handle negatives)

Both Floyd-Warshall and Bellman-Ford handle negative edges. Bellman-Ford finds shortest paths from a single source in O(nm)O(nm) time. Floyd-Warshall finds shortest paths from all sources in O(n3)O(n^3) time. Use Bellman-Ford if you need paths from one source.

Use Floyd-Warshall if you need all-pairs distances or have many queries. Bellman-Ford is better for sparse graphs with one query. Floyd-Warshall is better for many queries.

Space complexity is O(n2)O(n^2) for the data structures used.