任意の2地点間の全経路探索について

質問

ネットワーク上においてダイクストラ法を使うと任意の２地点間の最短経路が求められますが、最短経路だけでなく最長経路など任意の２地点間における全ての経路を求めたいと考えていますが、なかなか良いアルゴリズムができません。詳しい方御教授お願いいたします。

回答No.2

tatsumi01

物凄く非能率な方法ですが。
求めたい２点（Ａ、Ｂとします）を除いて、残りの地点の順列を求めます。地点数をＮとすれば（Ｎ－２）！通りできます。
この順列の先頭にＡ、末尾にＢを追加した順列の全てについて経路を求めれば良いと思います。ただし、一つの順列において相隣る２地点間に枝がなければ、その順列を捨てます。

回答No.1

secretd

あまり詳しいわけではないですが．
ダイクストラアルゴリズムで問題になるネットワークには大概閉路があったりするわけですが，そこの辺りはどのように考えていらっしゃるのでしょう．閉路をぐるぐる回ったら，コストは無限大になりますよね．
そうではなく，一筆書きみたいなものを考えるんだったら，巡回セールスマン問題みたいな考え方をすればいいんじゃないのでしょうか．