Re: [問題] longest path

[tkcn (小安)]

※ 引述《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
推 CMturtle:謝謝你們>"<  清大的學長耶~~
→ yoco315:113 發文, 112 跟 114 回答, 太溫馨了 QQ
推 yauhh:那如果是將A-C,C-B的longest path以union方式銜接,可以解嗎?
推 ledia:A-D-C, C-D-B 是 longest path, 要怎麼 union ?
→ yauhh:這你不用管.
※ 編輯: tkcn            來自: 140.114.78.231       (11/01 13:59)
推 LPH66:或許A-B的longest path其實是A-E-B 而E卻不在A-C C-B當中
推 ledia:喔喔, y 版友真是偉大 m(_ _)m
推 zerodevil:y大師說的是 受教了