現在、ブースト グラフ ライブラリのダイクストラ アルゴリズムhttp://www.boost.org/doc/libs/1_53_0/libs/graph/doc/dijkstra_shortest_paths.htmlを使用して、頂点のペア間の最短距離パスを計算しています。これまでのところ、先行マップに格納されている最短パスを 1 つしか取得できません。
だから私の質問は次のとおりです。関数が頂点のペア間のすべての可能な最短パスを返すようにすることは可能ですか?
質問する
1100 次
1 に答える
1
いいえ、自分で構築する必要があります。1 つの方法は、Dijkstra への 2 つの呼び出しを使用して、ソース頂点 s (G) からシンク頂点 t までの距離 (つまり、転置グラフの t からの距離) を計算することです。次に、距離(s, u) + 距離(u, t) = 距離(s, t) となるノード u と、距離(s, u) + 長さ (u, v) となるアーク uv を正確に含むサブグラフを抽出します。 ) + distance(v, t) = distance(s, t) となり、このサブグラフのすべての st パスを再帰的に列挙します。
于 2013-04-17T20:49:26.660 に答える