※ 引述《mqazz1 (无法显示)》之铭言： : Johnson的演算法那部分 有这个图 : http://ppt.cc/1(V; 最左边的那个node是新加入的node : 然後有一些问题 : 1. 如何及时发现，原graph有negative cycle ? : 如果我回答，跑n次Bellman-Ford，发现有新的node被relaxtion，这样算及时吗 Johnson = 一次 Bellman-Ford + reweighting + n次 Dijkstra 跑完 Bellman-Ford 的时候，就可以顺手侦测负环（可以跟reweighting一起做） 侦测负环的方法应该会在 Bellman-Ford 的章节... : 2. 上面那个图，新加的一node造成新的graph，是否会产生新的negative cycle ? 详细来说是新加 一个node 与 n条edge， 而且这些 edge 权重都是零，而且只有单向，只去不回， 因此不会产生新的negative cycle。 : 3. 上面那个图，新加的node作用是在做甚麽? 不加可以吗? 加node与edge是为了避免不连通。 不加的话， 图上任选一node当起点，跑 Bellman-Ford，起点走不到的node就没算到了。 接下来的 reweighting 与 n次Dijkstra 就一定会有问题。 : 谢谢 不客气 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.168.20.152 ※ 编辑: DJWS 来自: 118.168.20.152 (09/07 12:57)