PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[請益] 街道型的Two Shortest Path

看板Prob_Solve (計算數學 Problem Solving)作者 (頭有點痛)時間14年前 (2010/05/09 01:10), 編輯推噓0(0推 0噓 6→)
留言6則, 4人參與, 最新討論串1/7 (看更多)
請問一下，如果在街道型的Shortest Path 該如何解 (如下圖) ╔═══╦═══╦═══→→Ｄ═╗ ║　　　║　　　║　　　↑　　　║ ║　　　║　　　║　　　↑　　　║ ║　　　║　　　║　　　↑　　　║ ╠═══╬═══→→→→↑═══╣ ║　　　║　　　↑　　　║　　　║ ║　　　║　　　↑　　　║　　　║ ║　　　║　　　↑　　　║　　　║ ╠═══→→→→↑═══╬═══╣ ║　　　↑　　　║　　　║　　　║ ║　　　↑　　　║　　　║　　　║ ║　　　↑　　　║　　　║　　　║ ╠Ｓ→→↑═══╬═══╬═══╣ ║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║ ╚═══╩═══╩═══╩═══╝ 假設情境S→D，那麼箭頭所指向的是最短路徑 如果S走到第一個十字路口時，不依照箭頭所指的路線 而繼續前進，該怎麼在求出最短路徑呢? 找過一些有關最短路徑的演算法，EX.Dijkstra..等等 但是，這些演算法所預設的路線長度皆不同 所以可以依據路線長度來計算出最短路徑 那麼如果以街道型的來規劃最短路徑，每條街區長度皆相同 該如何去算出最短路徑? 曾經有想過要以角度來規畫出最短路徑， 但是，後來想到如果S和D在不同象限的話 那麼可能推出來的就不太一樣了 不曉得各位有沒有甚麼比較好的想法呢? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.175.197.82
→
05/09 01:28, , 1F
不浪費步的話，怎麼走都最短吧。
05/09 01:28, 1F
→
05/09 01:41, , 2F
但是，也不能多繞路，以上面圖形為例，S到第一個路口
05/09 01:41, 2F
→
05/09 01:41, , 3F
如果往下走的話，就算是繞遠路了，而不是最短路徑
05/09 01:41, 3F
→
05/11 22:50, , 4F
我問一個問題喔……你知道自己在講什麼嗎？
05/11 22:50, 4F
→
05/30 19:46, , 5F
你弄錯了吧，Dijkstra是可以用來解不同權重的最短路徑，
05/30 19:46, 5F
→
05/30 19:46, , 6F
不代表他只能解不同權重的路徑
05/30 19:46, 6F
‣ 更多 MrGG 的文章
文章代碼(AID): #1BvPiZg9 (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 7 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共7篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 MrGG 的文章
文章代碼(AID): #1BvPiZg9 (Prob_Solve)