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

[archon (三腳貓的把戲)]

　一般常用的最短路徑演算法就是 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
→ callisto2:可以參考 fault tolerant routing and shortest path
→ archon:拜收
> -------------------------------------------------------------------------- <

作者: LPH66 ((short)(-15074)) 看板: C_and_CPP
標題: Re: [問題] 考慮禁轉的最短路徑演算法...
時間: Mon Mar 15 11:59:29 2010

※ 引述《archon (三腳貓的把戲)》之銘言：
: 　一般常用的最短路徑演算法就是 Dijkstra Algorithm，
: 　原理相信各位前輩都比我清楚，就不在此贅述了。
: 　不過，在實際應用上，有時會遇到某些路徑的限制（譬如說道路的禁轉），
: 　某些該 relax 的點被限制不能拜訪，就破壞了 Dijkstra 演算法的特性。
: 　舉個例子來說：
:       |   |     假設 A->B->F 這是一個禁左轉的路口，
:    ---C---D---　Dijkstra 是無法規劃出 A->B->C->D->E->B->F 這樣的結果。
:       |   |
:   F---B---E---
:       |   |
:       A
: 　請問這樣子的問題，是被稱做什麼樣的問題呢？有關鍵字嗎？
: 　或者是，有什麼演算法適用這種問題呢？
這樣的話我會把 B 拆成四個點

B1 B2 B3 B4

分別有四個方向的單向邊連進來

連出去則是可以轉的方向

所以就會變成

A→B1→E,C
E→B2→C,F
C→B3→F,A
F→B4→A,E

這樣就可以正確跑出 A→B1→C→D→E→B2→F 的路線

--
実琴：「河野！你真的就這樣被物質慾望給吸引過去了嗎?!」
亨：「只要穿著女裝擺出親切的樣子，所有必要花費就能全免，似乎一點都不壞啊。」
実琴：「難道你沒有男人的尊嚴了嗎?!」
亨：(斷然道)「沒有。在節衣縮食且生活吃緊的學生面前，沒有那種東西。」
                                            －－プリンセス・プリンセス  第二話

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.30.84
→ walker2009:agree
推 loveme00835:同意