Re: [請益] TWO Shortest Paths
看板Prob_Solve (計算數學 Problem Solving)作者windows2k (KERORO軍曹)時間18年前 (2006/06/22 23:18)推噓5(5推 0噓 1→)留言6則, 4人參與討論串2/15 (看更多)
※ 引述《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
推
06/22 23:26, , 1F
06/22 23:26, 1F
→
06/22 23:27, , 2F
06/22 23:27, 2F
推
06/22 23:28, , 3F
06/22 23:28, 3F
推
06/22 23:51, , 4F
06/22 23:51, 4F
推
06/23 00:18, , 5F
06/23 00:18, 5F
推
06/23 00:20, , 6F
06/23 00:20, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 15 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章