※ 引述《CMturtle (傑尼龜)》之銘言： : 是說~~~一般最短路的演算法為什麼不能處理最長路阿？？ : 我的想法是 : 在無相圖中會出現正環的關係 : 但是如果再「有向無環圖」（DAG）中 : 是不是就可以套用最短路的算法來寫最長路？ : 而bellman-ford & SPFA應該也可以再有向圖中來判斷正環囉？？ 最短路徑演算法(不管哪一個)的核心概念是動態規畫 Dynamic Programming 而要能夠做 DP 的題目必須要有「最佳子結構」或「重疊子問題」 這代表我可以把一個題目拆成比較「小」的數個類似題 前者是這些小問題的最佳解可以構成我們的最佳解 後者則是這些小問題會一再地重覆計算 這裡的小並不一定是數字上的小 也許是數量上的少等等 (和遞迴的概念幾乎相同 只不過計算方向上遞迴是 top-down 而 DP 是 bottom-up 而已) 最短路徑問題上 單源非負最短路徑的「小」問題是起始點到稍近一點的點的距離 這是「重疊子問題」 其他的最短路徑的「小」問題則是只經過 k 號以前中介點的最短距離 這是「最佳子結構」 但最長路徑這個問題並沒有如此的性質 我們並不能找到一些「小」的最長路徑問題的結果能夠拿來構築原來的最長路徑 因此必須另尋他法來解決這個問題 而這些其他方法中也許需要其他演算法來偵測正圈 但解題的演算法主體並不會是它們 -- 実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」 亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」 実琴：「難道你沒有男人的尊嚴了嗎?!」 亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」 －－プリンセス・プリンセス 第二話 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.92