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
