Dijkstra 为什么要求非负权
Dijkstra 要求边权非负，是因为【0】。
⚠️ 负权边上跑 Dijkstra 会怎样
图里有负权边还硬跑 Dijkstra，结果是【0】。
出现负权该换成什么
图里确实有负权边时，应该换成【0】。
⚠️ 一个四点的反例
有向图：0→1 长 4、0→2 长 5、2→1 长 -3、1→3 长 1。运行 Dijkstra，看它给出的距离表： import heapq def dijkstra(g, s): INF = 10 ** 9 d = {
正确答案应该是多少
把 0 到 3 的所有路径都枚举一遍，取最短的。运行下面这段程序： def brute(g, s, t): INF = 10 ** 9 best = [INF] def go(u, c, seen):
让 Dijkstra 在这个反例上跑一遍
补全 dijkstra（照课本写法：弹出即定死），在那个有负权边的图上跑，输出它给 3 号的距离。
写一个暴力枚举当标尺
补全 brute：把从 s 到 t 的所有不重复经过点的路径都走一遍，取最小的总长。
⚠️ 这一次，对拍的结果是"不一致"
把 Dijkstra 和暴力枚举都写出来，在那个有负权边的图上各求一次 0 到 3 的距离。 输出三样：Dijkstra 的答案 / 暴力的答案 / 两者是否相同（相同输出 结果一致，否则 结果不一致）。
Bellman-Ford 的做法
Bellman-Ford 的做法是【0】。
为什么正好是 n-1 轮
Bellman-Ford 松弛 n-1 轮就够了，因为【0】。