作者DJWS (...)
看板Prob_Solve
標題Re: [請益] 街道型的Two Shortest Path
時間Sun May 9 11:32:44 2010
1F：推 MrGG:當初的構想是，因為人們在都市使用GPS導航，但是GPS的重新 05/09 10:42
2F：→ MrGG:定位需要一段時間，然後封包在傳遞時，盡可能的不要中斷 05/09 10:43
3F：→ MrGG:所以才想要找出另一條可能的最短路徑，防止駕駛臨時變換路線 05/09 10:44
4F：→ MrGG:所以當GPS導航出一條路線時，在每個路口，需要找出另一條可能 05/09 10:45
5F：→ MrGG:的最短路線，以防止駕駛者臨時改變路線 05/09 10:45
6F：→ MrGG:然而找過一些資料，在道路的拓墣上幾乎道路長短皆不同 05/09 10:48
7F：→ MrGG:因此很容易規劃出最短路線，然而我想到的是使用田字型來減少 05/09 10:48
8F：→ MrGG:未來模擬時的複雜度，但是 衍伸出的就是每條路的長度皆相同 05/09 10:49
9F：→ MrGG:不知道該怎麼去算出最短路線 05/09 10:49
道路長短皆不同的時候，很容易找出最短路線。
道路長短皆相同的時候，反而不知道怎麼找出最短路線。
你真的了解拓墣圖的最短路線的找法？
這個問題看起來不是你所謂的「找兩條最短路徑」，這樣講太籠統了。
根據你的問題描述，這個問題應該等同於：
「先找出起點到終點的一條最短路徑，
然後，找出這條最短路徑上的每一個路口到終點的次短路徑。」
你想找一條最短路徑，找很多條次短路徑。
應該是這樣吧？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.158.231