graph - 特定のコストを持つ無向グラフのパスを見つける

Question

無向の加重グラフがあるとします。私たちの仕事は、2 つの頂点 (始点と終点) 間の総コスト = N となるすべてのパスを見つけることです。BFS または DFS と組み合わせた修正ダイクストラのアルゴリズムを使用して実行できると思いますが、そのようなことを実装する方法がわかりません。助けてくれてありがとう。

Answer 1

グラフ データ構造を作成し、それをトラバースするためのフレームワーク/ライブラリがあると仮定すると、リソースの制約を超えた場合、バックトラックの深さ優先検索を実行して早期リターンを得ることができます。擬似コード:

void DFS(Vertex current, Vertex goal, List<Vertex> path, int money_left) {
  // oops
  if (money_left < 0) 
     return;

  // avoid cycles
  if (contains(path, current)
     return;

  // got it!
  if (current == goal)) {
     if (money_left == 0)
         print(path);
     return;
  }

  // keep looking
  children = successors(current); // optionally sorted from low to high cost
  for(child: children)          
      DFS(child, add_path(path, child), money_left - cost(child));      
}

そして、あなたはそれを次のように呼び出すことができますDFS(start, goal, List<Vertex>(empty), N)