作者windows2k (KERORO軍曹)
站內Prob_Solve
標題Re: [請益] TWO Shortest Paths
時間Thu Jun 22 23:24:28 2006
※ 引述《ericbibo (^^)》之銘言：
: 我們必須從給定的起點 S 到終點 T 中，
: 找 "兩條" 沒有重疊的minimum weight shortest paths。
: (也就是這兩條paths沒有經過相同的edges，且total weight值最小。)
: 可是，假如我現在把題目改成:
: 找"兩條"沒有重疊的minimum weight shortest paths，
: 一條由給定的起點 S1 到終點 D1，
: 另一條由起點 S2 到終點 D2 的話，
: 有沒有什麼方法可以解決這個問題呢?
我不是高手, 我只是來賺賭本的窮光蛋 囧rz
如果我沒搞錯題意的話
假設你會解原先的問題的話, 可以把後來這個問題轉成前一個問題
新增兩個節點, source 和 sink
新增四個邊 (source, S1) weight = 0, cap = 1 (u,v)代表一個從u到v的有向邊
(source, S2) weight = 0, cap = 1
(D1, sink) 同上
(D2, sink) 一樣同上,
就把原來的問題轉成從 source 到 sink,
找 "兩條" 沒有重疊的minimum weight shortest paths
--
多打一點字, 看有沒有多一點批幣
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.220.140
1F：推 ericbibo:可是這樣會找到一條由S1到D2，一條卻由 140.116.82.205 06/22 23:26
2F：→ ericbibo:S2到D1的paths 140.116.82.205 06/22 23:27
3F：推 windows2k:對喔, 在想想140.115.220.140 06/22 23:28
4F：推 SCSonic:XD 61.62.37.245 06/22 23:51
5F：推 windows2k:XDXD140.115.220.140 06/23 00:18
6F：推 bafu:XDXDXD 140.116.82.219 06/23 00:20