Re: [問題] longest path
看板Prob_Solve (計算數學 Problem Solving)作者SuBaRaSi (dddddddd)時間14年前 (2010/11/02 16:57)推噓2(2推 0噓 0→)留言2則, 1人參與討論串5/5 (看更多)
: 回答一：
: 因為最短路和最長路的性質不同。
: 最核心的差異是：最短路隨便截一段還是最短路，最長路隨便截一段通常不是最長路。
: 最短路的演算法，就是用上述性質推導出來的。
: 這個性質就是前面板友所說的 optimal substructure！
: 最長路之所以很難算，就是因為我們找不到它的 optimal substructure，只能用窮舉法。
: 回答二：
: 可以的！在DAG裡面，最長路隨便截一段就是最長路。
: 為什麼呢？因為DAG只能傻傻往一個方向前進，不會有繞路、繞圈圈的情形。
: 有沒有正環應該不是主因。
: 回答三：
: 可以的！不過並不是你推論的那樣。
: Bellman-Ford演算法和SPFA都可以判斷圖上有沒有負環。
: 把圖上每條邊權重變號，不就可以判斷圖上有沒有正環？
補充一下
在允許負邊, 比較general的graph上, 最長路和最短路的性質其實是一樣,對稱的
在這樣的graph上
longest 'simple' path和 shortest 'simple' path同樣是np-hard
longest path和shortest path(不要求simple)都是 in P
之前幾篇文指的最長路應該都是指'最長簡單路', 需要強調一下
正環和負環性質都是對稱的, 直接用bellman-form找最長路就可以測正環的存在
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.55.210
推
11/05 23:49, , 1F
11/05 23:49, 1F
推
11/05 23:52, , 2F
11/05 23:52, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 5 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
