作者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