Dijkstra 算法为什么一遇到负权边就会翻车
最短路问题听起来很直觉：从起点出发，找一条总代价最小的路。Dijkstra 算法的聪明之处在于，它每次都挑当前看起来最近的那个点，并且一旦挑中，就把它的答案“封死”，以后不再改。
这在所有边权都不为负时很合理。因为你已经是当前最近的点，后面再绕一圈只会更远，不可能突然变便宜。算法靠的不是运气，而是这个保证：路越走，总代价只会增加。
麻烦出在负权边。假设你先走到 A，花费 5；走到 B，花费 10。Dijkstra 会觉得 A 已经稳了。但如果后面从 B 有一条边到 A，权重是 -100，那 B 绕过去反而能把 A 的距离变成 -90。之前“封死”的答案直接变成垃圾。
所以 Dijkstra 的核心限制不是“实现不够聪明”，而是它的前提被破坏了。它相信已经选出的最近点不会被未来推翻，而负权边专门打碎这个信任。遇到负权边，要换 Bellman-Ford 这类允许反复修正答案的算法；如果还有负环，那最短路本身可能就不存在，因为你可以一直绕圈，把代价降到无限小。
#CS
最短路问题听起来很直觉：从起点出发，找一条总代价最小的路。Dijkstra 算法的聪明之处在于，它每次都挑当前看起来最近的那个点，并且一旦挑中，就把它的答案“封死”，以后不再改。
这在所有边权都不为负时很合理。因为你已经是当前最近的点，后面再绕一圈只会更远，不可能突然变便宜。算法靠的不是运气，而是这个保证：路越走，总代价只会增加。
麻烦出在负权边。假设你先走到 A，花费 5；走到 B，花费 10。Dijkstra 会觉得 A 已经稳了。但如果后面从 B 有一条边到 A，权重是 -100，那 B 绕过去反而能把 A 的距离变成 -90。之前“封死”的答案直接变成垃圾。
所以 Dijkstra 的核心限制不是“实现不够聪明”，而是它的前提被破坏了。它相信已经选出的最近点不会被未来推翻，而负权边专门打碎这个信任。遇到负权边，要换 Bellman-Ford 这类允许反复修正答案的算法；如果还有负环，那最短路本身可能就不存在，因为你可以一直绕圈，把代价降到无限小。
#CS
