最短路問題: ダイクストラ法の探索方向と探索範囲

ダイクストラ法は始点から近い順に(幅優先探索的に)探索していくため、終点が遠いところにあるP2P最短路問題では、到達するまでにほとんどの枝を探索してしまうことになる。

図は左から、始点→終点(Forward-Search)、終点→始点(Backward-Search)、始点⇔終点(Bidirectional-Search)の探索範囲を表しているが、明らかに「始点⇔終点」の探索範囲が狭い事が分かるだろう。

探索範囲を狭めることができれば、ポテンシャルの更新や、優先キューの操作を削減できる。前処理により疎化したグラフを作成する理由もこういった考えからであろう。

しかしながら、そうでもないということをこれから説明を行っていく。