Negative edge lengths and all pairs shortest paths (Fundamental algorithms, Spring 2023, Lecture 8)
Kent Quanrud · 77:36
This lecture shows why Dijkstra and “add a constant to every edge” fail once edges can be negative, then builds a complete toolkit: a structural lemma that finite distance is attained by a path (otherwise −∞ via a neg...