Re: [請益] TWO Shortest Paths
看板Prob_Solve (計算數學 Problem Solving)作者yoco315 (眠月)時間18年前 (2006/06/24 04:19)推噓0(0推 0噓 0→)留言0則, 0人參與討論串4/15 (看更多)
請問有現存的最短路徑演算法滿足以下條件的嗎？
1. node 可以重複
2. link 不可以重複
最短路徑演算法的比較我都已經忘光光了 XDDDDDD
假設我們已經知道上面這種演算法好了，先叫他作 A1
那我們可以根據這個演算法實作出一個變形，
除了起點 s 跟終點 e ，還可以接受第三個參數 "必經點" c，
我們叫這個演算法 A2。
A2 的方法是把 c 分開成兩點, c' 跟 c", (c消失)
c' 跟 c" 中間加上一條 link CL, CL 的 weight 極低，
而所有本來跟 c 相鄰的 node, 我們加上 link 使其依然跟 c', c" 相鄰，
這樣只要對 s 跟 e 作 A1, 得到的路徑就一定會經過 CL。
現在我們已經有 A2，
提供以下功能：找到 s 經過 c 到 e 的最短路徑。
此時令起點為 S，終點為 S，必經點為 E，
就可以求得一個從 S 出發跟結束, 而且一定經過 E 的 loop.
這個 loop 在 S 跟 E 的兩邊的部分，就是所求的兩條路徑。
(路徑和最短,沒有重複的link,且起點跟終點相同.)
然後是 S1 → E1, S2 → E2 這題...
在 E1 跟 S2 中間加一條 link T, weight 極低
施行 A1 ( S1, E2 ), 一定會經過 T,
就可以得到一條 S1 → E1 → S2 → E2 的路徑，
紫色部分就是答案。
============================================================
這樣有沒有錯？ 我不知道 XDDDDDDDD
--
To iterate is human, to recurse is divine.
遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.129.180
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 4 之 15 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
