Does Floyd-Warshall produce correct distances when some edge weights are negative?

## The condition, stated exactly The requirement is **no negative-weight cycle**, not **no negative-weight edge**. Those are different constraints and conflating them is the single most common error on this topic. A directed graph may be riddled with negative edges and still have perfectly well-defined shortest paths, as long as no closed loop of edges sums to less than zero. Why the distinction matters: shortest paths are only well defined when a cheapest route exists. If some cycle has negative total weight and lies on a route from `i` to `j`, you can go round it again and again, each lap lowering the total. The infimum is minus infinity and no path attains it — so the question "what is the shortest distance" has no answer to compute, in this or any algorithm. ## Why the recurrence tolerates negative edges The algorithm's state is "cheapest cost from `i` to `j` using intermediates only from the permitted set", and it grows that set one vertex at a time. At every step it makes a pure comparison: is the stored value beaten by routing through the newly permitted waypoint? Nothing is ever declared final; every cell stays open to improvement until the last waypoint has been considered. That matters because a negative edge means a longer route can be cheaper. An algorithm that commits — that picks the currently cheapest frontier vertex and treats its distance as settled — depends on the assumption that extending a route never lowers its cost. Drop that assumption and the commitment is unsound: a route that looked expensive early can become the winner once a negative edge downstream is taken into account. Floyd-Warshall makes no such commitment, so it needs no such assumption. The only thing it does assume is the one that justifies its two-way split of the recurrence: that a shortest route using waypoint `k` uses it exactly once, which holds precisely when removing a cycle never increases cost — that is, when no cycle is negative. ## The all-pairs consequence This is where the algorithm earns its place rather than merely being convenient. On a graph with negative edges and no negative cycle, running a greedy single-source search once per vertex does not give you a slower correct answer; it gives you a **wrong** answer, quietly, for the pairs whose best routes take a negative edge late. If you need every pairwise distance on such a graph, your realistic options are one Floyd-Warshall run, or an edge-relaxation single-source method repeated per source, or a reweighting scheme that shifts all weights non-negative using potentials computed by one relaxation run and then applies a fast greedy search per source. Which of those wins is a density question: the reweighting route is asymptotically better on sparse graphs, while the triple loop wins on dense ones with small vertex counts and is far shorter to write and to review. ## Reading the output when the condition is violated Run the algorithm on a graph that does contain a negative cycle and it does not hang or crash — it produces a matrix full of numbers that are not distances. The tell is on the diagonal: a cell `D[i][i]` below zero says a negative-weight cycle is reachable from `i` and returns to it, since a genuine cheapest round trip cannot cost less than nothing. Any pair whose best route can enter that cycle has a meaningless value. This is a check on a precondition, not a feature to lean on; when detecting and characterising such cycles is the actual goal, that is a different algorithm's job, and one worth naming explicitly rather than inferring from a diagonal. Two practical cautions. First, if unreachable pairs are stored as a large sentinel rather than a true infinity, negative edges can drag those sentinels downward and manufacture routes that do not exist — guard the update so a sentinel plus anything stays a sentinel. Second, on an undirected graph a single negative edge is *already* a negative cycle, because you can traverse it back and forth; negative weights therefore only make sense on directed graphs. ## Where negative weights come from in real models They are not exotic. Any cost model with credits produces them: a routing leg that recovers energy on a downhill run, a transfer that earns a rebate, a step that returns a deposit. Whenever the modelled quantity can be gained as well as spent, the graph has negative edges and the question of whether the cycle condition holds becomes an explicit modelling obligation — usually discharged by an argument about the domain, such as "you cannot recover more energy than you spent going up", rather than by a runtime check.