作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] Johnson跟reweight
时间Tue Sep 6 20:45:41 2011
Johnson的演算法那部分 有这个图
http://ppt.cc/1(V; 最左边的那个node是新加入的node
然後有一些问题
1. 如何及时发现，原graph有negative cycle ?
如果我回答，跑n次Bellman-Ford，发现有新的node被relaxtion，这样算及时吗
2. 上面那个图，新加的一node造成新的graph，是否会产生新的negative cycle ?
3. 上面那个图，新加的node作用是在做甚麽? 不加可以吗?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.24.198