Re: [請益] TWO Shortest Paths

[yalight (ㄚ光)]

※ 引述《yalight (ㄚ光)》之銘言：
: ※ 引述《yalight (ㄚ光)》之銘言：
: : 如果我沒記錯的話 好像是這樣:
: : 先找 S 到 T 的最短路徑, 假設是 cost1,
: : 然後把這條最短路徑的方向反向, weight 變負的
: : (就是 max flow 那樣算 residual network)
: : 然後再找 T 到 S 的最短路徑 cost2,
:            ^^^^^^ S 到 T 才對...囧
: : 然後 cost1 + cost2 就是答案~
: : 求最短路徑的方法可用 Dijkstra 還是偷懶用 Floyd Washall..
: : 因為雖然會有 negative edge 但是不會有 negative cycle,
: : 所以可以安心的用 @@:
: : 有錯請指教 m(_ _)m

這問題應該可以 reduce 成 min-cost max-flow problem(更難).
但是 min-cost max-flow 有 polynomial solution.

所以可以證明這題不是 NP 問題...

reduce 方法:
就把他想成 source 的 capacity = 2, edge 的 capacity = 1,
edge 上的 cost 就是 weight, 的 min-cost max-flow problem。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.19
※ 編輯: yalight         來自: 140.115.205.19       (06/24 16:48)
推 march20:一定是 NP, 但不一定是 NP-complete
推 march20:只要是 P, 就是 NP...
推 march20:P is a subset of NP
推 march20:but we don't know if it's proper subset