Re: [問題] longest path
看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間14年前 (2010/11/01 01:02)推噓6(6推 0噓 2→)留言8則, 6人參與討論串3/5 (看更多)
※ 引述《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
推
11/01 01:09, , 1F
11/01 01:09, 1F
→
11/01 06:20, , 2F
11/01 06:20, 2F
推
11/01 09:25, , 3F
11/01 09:25, 3F
推
11/01 09:52, , 4F
11/01 09:52, 4F
→
11/01 10:04, , 5F
11/01 10:04, 5F
※ 編輯: tkcn 來自: 140.114.78.231 (11/01 13:59)
推
11/01 17:16, , 6F
11/01 17:16, 6F
推
11/02 10:03, , 7F
11/02 10:03, 7F
推
11/02 15:56, , 8F
11/02 15:56, 8F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 5 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
