[問題] longest path

看板Prob_Solve作者 (傑尼龜)時間13年前 (2010/11/01 00:19), 編輯推噓2(2推 0噓 0→)
留言2則, 1人參與, 最新討論串1/5 (看更多)
是說~~~一般最短路的演算法為什麼不能處理最長路阿？？ 我的想法是 在無相圖中會出現正環的關係 但是如果再「有向無環圖」（DAG）中 是不是就可以套用最短路的算法來寫最長路？ 而bellman-ford & SPFA應該也可以再有向圖中來判斷正環囉？？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.91.133
推
11/01 01:16, , 1F
呃, 話說 longest path 是 NP-complete problem XD
11/01 01:16, 1F
推
11/01 01:18, , 2F
除非是特例
11/01 01:18, 2F
‣ 更多 CMturtle 的文章
文章代碼(AID): #1CpPSJu- (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 5 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 CMturtle 的文章
文章代碼(AID): #1CpPSJu- (Prob_Solve)