※ 引述《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)