Negative-Weight Shortest Paths in Near-Linear Time
Bernstein–Nanongkai–Wulff-Nilsen (FOCS 2022) — low-diameter decomposition + scaling + potentials, then plain Dijkstra
New graph
plant a negative cycle
◀ Prev
Next ▶
▶ Auto-play
negative edge
non-negative edge
LDD cut edge
shortest-path tree