作者yalight (ㄚ光)
站内Prob_Solve
标题Re: [请益] TWO Shortest Paths
时间Sat Jun 24 16:46:26 2006
※ 引述《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)
1F：推 march20:一定是 NP, 但不一定是 NP-complete 71.136.254.138 06/24 16:58
2F：推 march20:只要是 P, 就是 NP... 71.136.254.138 06/24 16:59
3F：推 march20:P is a subset of NP 71.136.254.138 06/24 16:59
4F：推 march20:but we don't know if it's proper subset 71.136.254.138 06/24 16:59