Re: [問題] longest path
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間14年前 (2010/11/02 00:21)推噓0(0推 0噓 0→)留言0則, 0人參與討論串4/5 (看更多)
※ 引述《CMturtle (傑尼龜)》之銘言：
: 是說~~~一般最短路的演算法為什麼不能處理最長路阿？？
: 我的想法是
: 在無相圖中會出現正環的關係
: 但是如果再「有向無環圖」（DAG）中
: 是不是就可以套用最短路的算法來寫最長路？
: 而bellman-ford & SPFA應該也可以再有向圖中來判斷正環囉？？
回答一：
因為最短路和最長路的性質不同。
最核心的差異是：最短路隨便截一段還是最短路，最長路隨便截一段通常不是最長路。
最短路的演算法，就是用上述性質推導出來的。
這個性質就是前面板友所說的 optimal substructure！
最長路之所以很難算，就是因為我們找不到它的 optimal substructure，只能用窮舉法。
回答二：
可以的！在DAG裡面，最長路隨便截一段就是最長路。
為什麼呢？因為DAG只能傻傻往一個方向前進，不會有繞路、繞圈圈的情形。
有沒有正環應該不是主因。
回答三：
可以的！不過並不是你推論的那樣。
Bellman-Ford演算法和SPFA都可以判斷圖上有沒有負環。
把圖上每條邊權重變號，不就可以判斷圖上有沒有正環？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.157.18
※ 編輯: DJWS 來自: 59.115.157.18 (11/02 00:36)
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
