Why doesn’t Dijkstra work with negative edge weights, and what can you use instead?

Answer

Dijkstra assumes that once a node has the smallest known distance, it will never improve later — negative edges break this assumption. Use Bellman–Ford for negative weights (and it can detect negative cycles).