作者mantour (朱子)
看板Prob_Solve
标题Re: [请益] 街道型的Two Shortest Path
时间Sun May 9 16:19:55 2010
※ 引述《MrGG (头有点痛)》之铭言：
: 请问一下，如果在街道型的Shortest Path 该如何解 (如下图)
: ╔═══╦═══╦═══→→Ｄ═╗
: ║ ║ ║ ↑ ║
: ║ ║ ║ ↑ ║
: ║ ║ ║ ↑ ║
: ╠═══╬═══→→→→↑═══╣
: ║ ║ ↑ ║ ║
: ║ ║ ↑ ║ ║
: ║ ║ ↑ ║ ║
: ╠═══→→→→↑═══╬═══╣
: ║ ↑ ║ ║ ║
: ║ ↑ ║ ║ ║
: ║ ↑ ║ ║ ║
: ╠Ｓ→→↑═══╬═══╬═══╣
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ║ ║ ║ ║ ║
: ╚═══╩═══╩═══╩═══╝
: 假设情境S→D，那麽箭头所指向的是最短路径
: 如果S走到第一个十字路口时，不依照箭头所指的路线
: 而继续前进，该怎麽在求出最短路径呢?
: 找过一些有关最短路径的演算法，EX.Dijkstra..等等
: 但是，这些演算法所预设的路线长度皆不同
: 所以可以依据路线长度来计算出最短路径
: 那麽如果以街道型的来规划最短路径，每条街区长度皆相同
: 该如何去算出最短路径?
哪里有写说这些演算法预设每条线段要不一样长的？
人家是说这些演算法在每条线段不一样长时，还是可以用
没有人说每条线段一样长就不能用
你每条线段都设为1
这些演算法都还是可以找出最短路径
: 曾经有想过要以角度来规画出最短路径，
: 但是，後来想到如果S和D在不同象限的话
: 那麽可能推出来的就不太一样了
: 不晓得各位有没有甚麽比较好的想法呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.57.65.2
※ 编辑: mantour 来自: 61.57.65.2 (05/09 16:23)