写一个暴力枚举当标尺
补全 brute：把从 s 到 t 的所有不重复经过点的路径都走一遍，取最小的总长。
阅读更多 →
让 Dijkstra 在这个反例上跑一遍
补全 dijkstra（照课本写法：弹出即定死），在那个有负权边的图上跑，输出它给 3 号的距离。
阅读更多 →
正确答案应该是多少
把 0 到 3 的所有路径都枚举一遍，取最短的。运行下面这段程序： def brute(g, s, t): INF = 10 ** 9 best = [INF] def go(
阅读更多 →
⚠️ 一个四点的反例
有向图：0→1 长 4、0→2 长 5、2→1 长 -3、1→3 长 1。运行 Dijkstra，看它给出的距离表： import heapq def dijkstra(g, s): INF
阅读更多 →
出现负权该换成什么
图里确实有负权边时，应该换成【0】。
阅读更多 →
⚠️ 负权边上跑 Dijkstra 会怎样
图里有负权边还硬跑 Dijkstra，结果是【0】。
阅读更多 →
Dijkstra 为什么要求非负权
Dijkstra 要求边权非负，是因为【0】。
阅读更多 →
⚠️ 最短的路 vs 最少的步
算出 0 到 4 的带权最短路，再和步数最少那条（0-2-4）比一比。 输出三样：最短总长 / 它走了几条边 / 步数最少那条的总长。
阅读更多 →
把最短路径还原出来
补全 dij_path：松弛成功时记下父亲，最后从终点倒着回溯。输出 0 到 4 的路径（用 - 连）。
阅读更多 →
写一个 Dijkstra
补全 dijkstra：用小根堆，弹出时先跳过已经处理过的点，再松弛它的每条边。
阅读更多 →