推 max1147:不能用矩陣那個算各點到各點最遠距離D1到D5來看嗎? 02/27 02:01
推 FRAXIS:圖應該是DAG吧 不然Longest Path 是NP-Complete 02/27 04:29
※ 編輯: rnbjacky 來自: 221.120.1.32 (03/07 11:29)
借問一下
因為常常聽到人有人說可以用BellmanFord去改
可是cormen書上很明確寫到
longest path problem 沒有 有效率的 Dynamic programming 解法
交大也有考過這個觀念
可是似乎BellmanFord真的可以改
不知道到底問題在哪(是不是沒cycle會對?)
到底是可不可以....
如果可以 為什麼書上沒有d.p的作法?
如果不可以 是哪邊會有問題.............
※ 引述《predatorK (predator')》之銘言：
: 今天政大資科考一題step by step找出圖形G上從u到v的longest path
: 我嘗試用Dijkstra's改成找longest path但答案是錯的
: 眼看時間所剩無幾
: 我只好這樣寫
: step1:張開你的雙眼
: step2:凝視圖形G 60sec
: step3:寫下答案
: 不知道這樣會有幾分?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.198.108