作者MrGG (头有点痛)
看板Prob_Solve
标题[请益] 街道型的Two Shortest Path
时间Sun May 9 01:10:57 2010
请问一下，如果在街道型的Shortest Path 该如何解 (如下图)
╔═══╦═══╦═══→→Ｄ═╗
║ ║ ║ ↑ ║
║ ║ ║ ↑ ║
║ ║ ║ ↑ ║
╠═══╬═══→→→→↑═══╣
║ ║ ↑ ║ ║
║ ║ ↑ ║ ║
║ ║ ↑ ║ ║
╠═══→→→→↑═══╬═══╣
║ ↑ ║ ║ ║
║ ↑ ║ ║ ║
║ ↑ ║ ║ ║
╠Ｓ→→↑═══╬═══╬═══╣
║ ║ ║ ║ ║
║ ║ ║ ║ ║
║ ║ ║ ║ ║
╚═══╩═══╩═══╩═══╝
假设情境S→D，那麽箭头所指向的是最短路径
如果S走到第一个十字路口时，不依照箭头所指的路线
而继续前进，该怎麽在求出最短路径呢?
找过一些有关最短路径的演算法，EX.Dijkstra..等等
但是，这些演算法所预设的路线长度皆不同
所以可以依据路线长度来计算出最短路径
那麽如果以街道型的来规划最短路径，每条街区长度皆相同
该如何去算出最短路径?
曾经有想过要以角度来规画出最短路径，
但是，後来想到如果S和D在不同象限的话
那麽可能推出来的就不太一样了
不晓得各位有没有甚麽比较好的想法呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.175.197.82
1F：→ bleed1979:不浪费步的话，怎麽走都最短吧。 05/09 01:28
2F：→ MrGG:但是，也不能多绕路，以上面图形为例，S到第一个路口 05/09 01:41
3F：→ MrGG:如果往下走的话，就算是绕远路了，而不是最短路径 05/09 01:41
4F：→ yoco315:我问一个问题喔……你知道自己在讲什麽吗？ 05/11 22:50
5F：→ ILYY:你弄错了吧，Dijkstra是可以用来解不同权重的最短路径， 05/30 19:46
6F：→ ILYY:不代表他只能解不同权重的路径 05/30 19:46