最小生成树是什么
一张连通图的最小生成树是【0】。
阅读更多 →
⚠️ 同一对算法，一张图一致、一张不一致
把 Dijkstra 和 Bellman-Ford 都写出来，在两张结构相同的图上各跑一次求 0 到 3 的距离： 把 2→1 那条边设成 +3（全是非负权） 把它设成 -3（有负权边） 各输出 结果
阅读更多 →
⚠️ 加上负环检测
补全 has_neg_cycle：先松弛 n-1 轮，再多试一轮——还能松弛成功就说明有负环。 验两张图，把两个结果拼起来输出（有负权边那张在前）。
阅读更多 →
写一个 Bellman-Ford
补全 bellman：把所有边松弛 n-1 轮。在那个有负权边的图上跑，输出整张距离表。
阅读更多 →
两张图，各有没有负环
一张是上一节那个有负权边的图，一张是 0→1:1、1→2:-1、2→1:-1（1 和 2 之间绕一圈是 -2）。运行下面这段程序： def has_neg_cycle(g, s): INF =
阅读更多 →
Bellman-Ford 在那个反例上
同一张有负权边的图，这次用 Bellman-Ford。运行下面这段程序： def bellman(g, s): INF = 10 ** 9 d = {u: INF for u in g
阅读更多 →
怎么判断图里有负环
用 Bellman-Ford 判断负环的办法是【0】。
阅读更多 →
为什么正好是 n-1 轮
Bellman-Ford 松弛 n-1 轮就够了，因为【0】。
阅读更多 →
Bellman-Ford 的做法
Bellman-Ford 的做法是【0】。
阅读更多 →
⚠️ 这一次，对拍的结果是"不一致"
把 Dijkstra 和暴力枚举都写出来，在那个有负权边的图上各求一次 0 到 3 的距离。 输出三样：Dijkstra 的答案 / 暴力的答案 / 两者是否相同（相同输出 结果一致，否则 结果不一致
阅读更多 →