グラフ内の任意のノードとルート/ソース間の最小距離を見つけることに興味があります。すべてのリンクには重みがあります。各ノードの親を知る必要がないため、ウィキペディアの記事previous[]に示されているを使用する必要はないと思います。あれは正しいですか？さらに、重みがすべて 1 に等しい場合、BFS を実行できますか?
1 に答える
3
バックポインタなしでダイクストラのアルゴリズムを実装することは完全に可能です。私は自分でやったので、これを知っています。:-) その結果、完了したら最短パスを復元することはできませんが、必要なパスの長さが完全に問題ない場合です。
2 番目の質問については、はい、BFS を単位重量で直接使用できます。ダイクストラのアルゴリズムは、すべてのエッジが同じ正のコストを持つ場合に、BFS で検出される順序でノードを訪問します。
于 2011-01-20T22:39:34.613 に答える