[問題] Johnson跟reweighting
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間13年前 (2011/09/06 20:45)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/3 (看更多)
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
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
