感谢大家对这个问题所提供的宝贵意见，我将目前的讨论串先做个整理。 (顺便赚点P币...XD) Problem A: 给一个无向图 G = (V, E)， 请试着在图上找两条 edge-disjoint minimum weight shortest paths。 一条由给定的起点 S1 到终点 T1；另一条由起点 S2 到终点 T2。 case 1: 若 S1=S2 且 T1=T2 这其实就是ACM Problem 10806的问题， yalight 在第100篇推文中，有清楚的介绍解法喔。 case 2: 若 S1=S2 或 T1=T2 这个case则可以利用 windows2k 在第96篇所提到的作法来解。 case 3: yoco315 在第98篇推文中提到， 首先在 T1 与 S2 之间加一条 directed edge e ， 而 e 的 weight 为 -∞，假设所得的新图为 G’。 若 G’不存在 negative weight cycle， 则利用 Bellman-Ford algorithm 找出由 S1 到 T2 的shortest path， 即为所求。 另外，yoco315 也将原先的 Problem A，转成下面的 Problem B。 Problem B: 在一个有向图 G 中，找一条由起点 S 到终点 T， 且经过某条特定的 directed edge e 的最短路径。 只要可以解出 Problem B 的话，相信 Problem A 也可以迎刃而解。 (有人对 Problem B 有什麽建议吗???) 此外，版主大人 march20 也为我们找到一些目前关於此 Problem A 相关文献。 首先在 Yossi 的 paper 中，讨论了以下这个问题 Problem C: 给定一个无向图 G = (V, E)，请问 G 是否存在两条 vertex-disjoint paths， 一条由起点 S1 到 T1，另一条由 S2 到 T2。 在 Problem C 中，我们考虑vertex-disjoint paths (也就是这两条paths不经过相同的vertices)， 且不去管每条edge的weight，只考虑paths的存在性。 则根据 Yossi 的论文， Problem C 可以在 O(|V|*|E|)的时间复杂度解决。 可是，Problem C 讨论的是 vertex-disjoint， 而我问的 Problem A 则是 edge-disjoint。 所以，自然而然就有了下面的 Problem D。 Problem D: 给定一个无向图 G = (V, E)，请问 G 是否存在两条 edge-disjoint paths， 一条由起点 S1 到 T1，另一条由 S2 到 T2。 事实上，Problem D 也有 polynomial-time solution 如下: 首先，我们先利用 Yossi 解 Problem C 的方法， 检查 G 有没有 vertex-disjoint paths，一条由 S1~>T1，另一条由 S2~>T2。 CASE 1: 如果 G 有 vertex-disjoint paths， 则代表 G 有 edge-disjoint paths。 (因为若这两条paths没用到相同的vertex，一定不会用到相同的edge) CASE 2: 如果 G 没有 vertex-disjoint paths， 在这个case下，G 会有 edge-disjoint paths，只有一种可能性。 那就是这两条 edge-disjoint paths，中间有通过相同的点 u。 在这个CASE下，我们新增一个点 w， 再多加四条edges，分别连接 w与S1, w与S2, w与T1, w与T2。 我把这个新的图叫 G'。 如此一来， w 与 u 之间，必存在四条 edge-disjoint paths。 (w-S1~>u, w-S2~>u, w-T1~>u, w-T2~>u)。 因此，我们只要利用 max-flow algorithm， 对每一个 G 上的点 v, 检查 w 与 v 之间是不是有四条 edge-disjoint paths， 就可以知道 G 有没有一条 S1~>T1， 另一条 S2~>T2 的 edge-disjoint paths 了。 换言之，我顶多执行 max_flow algorithm O(|V|)次， 即可知道 G 有没有 edge-disjoint paths。 因此，Problem D has a polynomial-time solution。 PS1: Problem D 的解法参考自 Y. Perl and Y. Shiloach, "Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph," Journal of ACM, vol. 25, no. 1, pp. 1-9, Jan. 1978. PS2: 经过这一串的讨论，让我对解出原先的 Problem A 又多了几分信心。 谢谢大家~ ^_______^ PS3: 不知道有没有哪里我疏忽没整理到的地方，或是哪边我误解了原PO的想法。 有错的话，也请不吝指教。 ------------------------------ 原来我一直在想这麽难的问题啊~ 我还以为我脑残咧... XD --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.116.82.205