PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] TWO Shortest Paths

看板Prob_Solve (計算數學 Problem Solving)作者ericbibo (^^)時間18年前 (2006/06/29 16:02)推噓4(4推 0噓 0→)

留言4則, 3人參與討論串15/15 (看更多)

感謝大家對這個問題所提供的寶貴意見，我將目前的討論串先做個整理。 (順便賺點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