Graph Theory37 sections · 1633 units
Open in Course

Handling Negative Edges

(Unlike Dijkstra it works)

Floyd-Warshall works with negative edge weights. Dijkstra does not. If your graph has negative edges but no negative cycles, Floyd-Warshall computes correct shortest paths. If there is a negative cycle, shortest paths are undefined (you can loop and reduce cost to negative infinity).

Floyd-Warshall can detect this. This makes Floyd-Warshall more general than Dijkstra, at the cost of higher time complexity.