Boostのグラフbreadth_first_search（）を使用して、重みのない無向グラフのパスを見つける

Question

私は、無向エッジと非加重エッジを持つadjacency_listグラフを使用しています。頂点uと頂点vの間の最短経路を見つける必要があります。 uからbreadth_first_search（）を使用する必要がありますか？ vに達したら、どのようにしてパスを取得し、どのように検索を停止しますか？

ありがとう！

Answer 1

最短パスアルゴリズムの1つ、 2つの頂点間のパスを見つける必要があるため、Dijkstra Shortest Path が最適です。 例がありますブースト分布での使用。その関数から出力を取得するためのオプションがいくつかあります：距離プロパティマップを提供するか、先行マップを作成するか、カスタムビジターを作成します。

Answer 2

はい、uからbreadth_first_search（）を実行します。

FOR every vertex i meet
  IF i==v: BREAK
  record predecessor of i as i.p

最短パスを見つけるには、v：から始めます。

PRINT_PATH(u, v)
  IF v==u
    print u
  ELSEIF v.p==NIL
    print 'no path from u to v exists'
  ELSE PRINT_PATH(u, v.p)
    print v

Answer 3

最小スパニングツリー：検索アルゴリズムを使用する必要があります。これは非常に単純で単純な欲張りアルゴリズムです。