作者tkcn (小安)
看板Prob_Solve
標題Re: [問題] longest path
時間Mon Nov 1 01:02:20 2010
※ 引述《CMturtle (傑尼龜)》之銘言：
: 是說~~~一般最短路的演算法為什麼不能處理最長路阿？？
因為最短路徑演算法是使用 Dynamic Programming，
而 DP 能解的問題必須具備 optimal substructure 特性。
以最短路徑來說，一條最短路徑隨意拆成兩段，
這兩段也會是最短路徑 (否則我們大可把原來路徑對應的一段替換為現在更短的這條)
但是最長路徑並沒有這種特性，以 A 到 B 來說，
即使我們能找到 A 到 C 的最長路徑以及 C 到 B 的最長路徑，
把這兩段合起來，卻不見得能得到 A 到 B 的最長路徑，
因為很可能有重復的 vertex。 (違反 simple path 定義)
: 我的想法是
: 在無相圖中會出現正環的關係
: 但是如果再「有向無環圖」（DAG）中
: 是不是就可以套用最短路的算法來寫最長路？
單就這問題，我想你看了上面的說明應該可以自己回答，所以我就不給答案了。
不過，在 DAG 中要求最短路徑或最長路徑，有更簡單的 DP 作法能達成。
: 而bellman-ford & SPFA應該也可以再有向圖中來判斷正環囉？？
如果你把 edge 的 weight 全部正負交換，然後偵測 negtive cycle，
或著修改 relax 改成紀錄較長的路徑，我想大概也能判斷的出來。
不過，簡單的 DFS/BFS 就能找出 positive cycle 了，
所以應該是沒什麼必要用 bellman-ford。
--
◤ ◥ ◢ ◣
T$，修好它吧。 ⊙▁⊙─ ─⊙▂⊙ 碰到問題，用SoftICE就對了！
╰ ∕皿﹨ ◥皿◤ ╯
◥█◤◢ ◥ ︶◤
Lee ◤ ︶ ◥◤ ﹨▼∕◥ T$ Chen
ＭＹＴＨＢＵＧＴＥＲＳ ◥ ◤＼◥ by dajidali
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
1F：推 CMturtle:謝謝你們>"< 清大的學長耶~~ 11/01 01:09
2F：→ yoco315:113 發文, 112 跟 114 回答, 太溫馨了 QQ 11/01 06:20
3F：推 yauhh:那如果是將A-C,C-B的longest path以union方式銜接,可以解嗎? 11/01 09:25
4F：推 ledia:A-D-C, C-D-B 是 longest path, 要怎麼 union ? 11/01 09:52
5F：→ yauhh:這你不用管. 11/01 10:04
※ 編輯: tkcn 來自: 140.114.78.231 (11/01 13:59)
6F：推 LPH66:或許A-B的longest path其實是A-E-B 而E卻不在A-C C-B當中 11/01 17:16
7F：推 ledia:喔喔, y 版友真是偉大 m(_ _)m 11/02 10:03
8F：推 zerodevil:y大師說的是 受教了 11/02 15:56