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