[問題] 考慮禁轉的最短路徑演算法...

看板C_and_CPP作者 (三腳貓的把戲)時間14年前 (2010/03/15 10:55), 編輯推噓0(0推 0噓 2→)
留言2則, 2人參與, 最新討論串1/2 (看更多)
　一般常用的最短路徑演算法就是 Dijkstra Algorithm， 　原理相信各位前輩都比我清楚，就不在此贅述了。 　不過，在實際應用上，有時會遇到某些路徑的限制（譬如說道路的禁轉）， 　某些該 relax 的點被限制不能拜訪，就破壞了 Dijkstra 演算法的特性。 　舉個例子來說： | | 假設 A->B->F 這是一個禁左轉的路口， ---C---D---　Dijkstra 是無法規劃出 A->B->C->D->E->B->F 這樣的結果。 | | F---B---E--- | | A 　請問這樣子的問題，是被稱做什麼樣的問題呢？有關鍵字嗎？ 　或者是，有什麼演算法適用這種問題呢？ -- 　追根究底所得到的東西，是失望的觀眾，以及狼狽的魔術師... De'Ring Practice http://www.wretch.cc/blog/miauwally/21246514 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.116.90.104
→
03/15 11:12, , 1F
可以參考 fault tolerant routing and shortest path
03/15 11:12, 1F
→
03/15 12:27, , 2F
拜收
03/15 12:27, 2F
‣ 更多 archon 的文章
文章代碼(AID): #1BdQ6z5g (C_and_CPP)
‣ 更多 archon 的文章
文章代碼(AID): #1BdQ6z5g (C_and_CPP)