为什么要求非负权
第 1 步：从 0 出发：1 号 4，2 号 5 第 2 步：1 号最近，定死；3 号得 5 第 3 步：取出 2 号：走负边到 1 号 第 4 步：1 号改成 2，可它已定死 第 5 步：没人再管 3 号：还是 5 0 1 2 3 d 0
负权边上硬跑会怎样
图里有负权边还硬跑 Dijkstra，结果是【0】。
出现负权该换成什么（C++）
图里确实有负权边时，应该换成【0】。
一个四点的反例
有向图：0→1 长 4、0→2 长 5、2→1 长 -3、1→3 长 1。运行 Dijkstra，看它给出的距离表： #include <algorithm> #include <iostream> #include
正确答案应该是多少
把 0 到 3 的所有路径都枚举一遍，取最短的。运行下面这段程序： #include <algorithm> #include <iostream> #include <queue> #include &
让它在反例上错一次
补全 dijkstra（照课本写法：弹出即定死），在那个有负权边的图上跑，输出它给 3 号的距离。 （本题用 g++ -std=c++17 -O0 编译。）
写一个暴力枚举当标尺
补全 go：把从 s 到 t 的所有不重复经过点的路径都走一遍，brute 取最小的总长。 （本题用 g++ -std=c++17 -O0 编译。）
对拍结果是不一致
Dijkstra 和暴力枚举都写好了，在那个有负权边的图上各求一次 0 到 3 的距离。补全暴力枚举里的 go，输出三样：Dijkstra 的答案 / 暴力的答案 / 两者是否相同（相同输出 结果一致，否则 结果不一致）。 （本题用 g++
Bellman-Ford 的做法
第 1 步：行是轮数，列是四个点 第 2 步：第 1 轮：所有边松弛一遍 第 3 步：第 2 轮：3 号改小了 第 4 步：第 3 轮：没有再变 第 5 步：不定死任何点，负边也扛得住 0 1 2 3 第1轮 第2轮 第3轮 0 2 5 5
为什么正好是 n-1 轮（C++）
Bellman-Ford 松弛 n-1 轮就够了，因为【0】。