Ｃ言語 経路探索 経路リストの作成

S→B→Ｃ → Ｄ →Ｇ
　　↓　 ↓→Ｅ→↑
　　→Ｆ→→↑

Start(S)からＧoal(G)までのとりうる全経路を自動作成するプログラムを
Ｃ言語で作成したいです。

上の例だと、
ルート1: SBCDG
ルート2: SBCEG
ルート3: SBFEG
の３つのルートを算出できるプログラムです。

節と節の接続情報は持っているものとします。
S→B
B→C
C→D
D→Ｇ
Ｃ→E
Ｅ→Ｇ
B→Ｆ
Ｆ→Ｅ

struct connectList{
int node1;
int node2;
}


struct root{
int nodeId;
int nodeCost;
root_t** next;
};


木構造のような構造体で作成していこうとしたのですが、
ひとつのS→Ｇまでのパスは作成できるのですが、
すべてのパスを求めるにはどうしたらよいのでしょうか？


データ構造、プログラムサンプルを教えていただけないでしょうか？

No.2 回答者： Tacosan 回答日時： 2013/01/18 14:53

普通はそんな感じでしょう＞#1. ただ, 分岐の有無を考えると却って面倒で, 常にスタックに積む方がシンプルだと思います.

一言で言えば「深さ優先探索」.

No.1 回答者： akayoroshi 回答日時： 2013/01/18 08:39

分岐があったら、それまでにたどった経路をスタックに積んで、一方の枝に進む。

目的に到達したら、スタックから下して、前に辿らなかったほうの枝に進む。
スタックが空になっていたら終わり。
というアルゴリズムはどうですか。