複数の最短経路を探索するアルゴリズムなどがありましたら教えてほしいです

Question

「A Star Search」という最短経路のアルゴリズムについて勉強したのですが、最短経路が複数ある場合それらすべてを返すアルゴリズムはありますでしょうか。ご存知でしたらご教授またはその説明がされているサイトがあれば教えていただきたいです。

具体的には下記画像のようなものなのですが、S（スタート）からG（ゴール）を目指す際に4パターンあると思うのですがこれらの経路を返すアルゴリズムはありますでしょうか。戻り値は「List<int[]>」みたいな感じです。
（int[]はマス？のIDの配列を表す感じです）
※下記画像は単純な経路ですが実際はもっと無駄な道などがあることを想定

よろしくお願いします。

Comments

[jbpb0]

> それらすべてを返すアルゴリズム

「すべて」というのは必須ですか?

[Zuishin]

幅優先で全探索すればすべて求められますね。実際には途中で枝刈りするので全て探索するわけではありませんが。

Answer 1

Googleで検索してみたら、二つ引っかかりました。

読んでみてはいかがですか。

The New Algorithm for Finding the Paths based on Coding Graph

New Strategies in Learning Real Time Heuristic Search

Answer 2

A*法なりであらかじめ最短経路上にありうるすべてのノードのスタートからの距離D(x)がわかるものとします。
ノードuからvへコストcの辺eがあるとしたとき、eが含まれるスタートからvまでの最短経路が存在するならD(u)+c == D(v)が成り立ち、その時の最短経路はスタートからuまでの最短経路にeを加えたものです。
グラフにコスト0以下の閉路がなければ最短経路上に存在するノードはトポロジカルソートできるので、順に最短経路を求めていけば、最終的にスタートゴール間の全最短経路が列挙できます。
ただし全最短経路を求めようとするとグラフによっては相当な数になるので、実用に耐えうるかは別の話です。