推 PsMonkey:好用功阿.... [推] 06/29 17:19
推 bafu:好文推一下（好帖我頂！？） XD 06/29 17:34
推 march20:可喜可賀 :> 06/30 01:52
感謝大家對這個問題所提供的寶貴意見，我將目前的討論串先做個整理。
(順便賺點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