liveBook · Manning

Negative-weight edge

As explained in Algorithms Every Programmer Should Know

A negative edge weight is a numerical edge cost less than zero in a weighted graph.

A negative-weight edge has a cost below zero. Floyd–Warshall can handle negative edge weights by reconsidering routes through intermediate vertices, provided the graph has no negative-weight cycles. Dijkstra’s algorithm does not handle negative edge weights. section 9.1 section 9.3

A negative-weight cycle is a closed loop whose total cost is below zero. Repeating that loop can reduce a path’s cost without limit, so no shortest path exists. After Floyd–Warshall runs, a negative diagonal entry signals such a cycle. section 9.3 section 9.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains how Floyd–Warshall accommodates negative edges and detects negative cycles, but gives no worked negative-edge calculation.
What you can do after
Diagnose negative-weight cycles by checking whether any distance-matrix diagonal entry is below zero after Floyd–Warshall runs.
How it connects
Contrasts negative edge handling in Floyd–Warshall and Dijkstra, and links negative edges to negative-weight cycles.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.