"前の"ベクトルのないダイクストラのアルゴリズム

Question

私は、グラフの任意のノードとルート/ソースの間の最小距離を見つけることに興味があります。すべてのリンクに重みがあります。私はprevious[]を使用する必要はないと思います。the Wikipedia articleで示されています。なぜなら、私は各ノードの親を知る必要がないからです。あれは正しいですか？さらに、ウェイトがすべて1に等しい場合、私はBFSを実行できますか？

Answer 1

バックポインタを使用しないダイクストラのアルゴリズムを完全に実装することは可能です。私はI've done it myselfのためこれを知っています。 :-)その結果、作業が終わっても最短パスを回復することはできませんが、必要なのはパスの長さだけです。

あなたの2番目の質問では、はい、ダイレクトでユニット重量のBFSを使用することができます。ダイクストラのアルゴリズムは、すべてのエッジが同じ正のコストを有する場合、BFSで遭遇するであろう順序でノードを訪問する。