かなり長い間読んで検索した後でも、マルチグラフの深さ優先トラバーサル (または検索) について理解できません(2 つの頂点が複数のエッジを持つことができます)。
私は別のSOの質問でこの答えを見つけました:
任意の 2 つの頂点間のすべての接続を検出するグラフ アルゴリズム
これは良い答えですが、単純なグラフにのみ適用されます。
要するに、頂点 A から頂点 B までのすべての単純なパス(頂点の繰り返しなし) が、最短パスだけでなく、 Multigraphに必要です。
私は、JGraphT を使用して Java でこれを実装しています。別の言語での解決策は気にしません。グラフは有向で重み付けされていますが、これも役立つ場合があります。
PS アルゴリズムの実行時間は気にしません (結果をキャッシュします)。
リンクされた質問のものと同様の出力を探しています(エッジに追加の情報がいくつかありますが、それはトラバーサルとはあまり関係ありません:
All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E
ありがとうございました。