重み付けされた有向非循環グラフのソースノードから他のすべてのノードまでの最短経路を見つけるのに、最適な方法でBFSを使用できますか？

私はそれがトポロジカルソートを使ってO（V + E）で実行できることを知っています。しかし、私はBFSを使って同じ複雑さでやり遂げることもできると思います。重み付けされた有向非循環グラフのソースノードから他のすべてのノードまでの最短経路を見つけるのに、最適な方法でBFSを使用できますか？

出典

2017-04-23 Aditya Joshee

あなたは（最も最適な方法で）何を意味するのですか？もしあなたが意味するものが複雑ならば、はい。トポロジカルな並べ替えはDFSのアプリケーションであり、その理由はO（V + E）の複雑さです。「私たちはBFSを使ってトポロジカルなソートを行うことができますか？」と問いかけるのは自然です。この質問は既に尋ねられています。 – Abdulhakeem

私は、ノードをトポロジカルな順序で訪問するのではなく、単にBFSを使うことができたことを意味しました。 –

トポロジカルな並べ替えは、1つのDFS実行であること以外は何もありません。次に各頂点が完成すると、リンクされたリストの前面に配置されます。実行時間はO（V + E）です。私が前に言ったように、私はここでは「BFSを使ってトポロジカルな並べ替えをすることができますか？これはすでに尋ねられ、答えられています。

あなたが意味するものが単なるBFSであれば、私はいいえと言います。これを見てくださいexample。トポロジカルソートは、グラフGにエッジ（u、v）が含まれている場合、uが順序付けの前にvのように表示されるように、すべての頂点の線形順序付けです。この例では、cからdのエッジがありますが、cの前にdが表示されています。トポロジカルなソートを見つけるためにBFSを更新できると思いますが、DFSを実行するのと同じ複雑さがあります。私はあなたにこのポストを見ることをお勧めしますUsing BFS for topological sort

出典

2017-04-25 16:42:24 Abdulhakeem

しばらくトポロジカルソートを忘れてみましょう。ソースノードsから始まるDAGの幅優先横断探索を使用すると、遠隔配列（無限に初期化された）を維持してO（V + E）時間内に他のすべてのノードまでの最短距離を見つけることができます。ノードに現在格納されている値よりも小さい値が得られます。だから私の元の質問に戻って、最短パスを見つけるためにDAGのノードを横断するためのトポロジカルな順序を使用するのと同じ複雑さのこのアプローチではありませんか？ –

重み付けされた有向非循環グラフのソースノードから他のすべてのノードまでの最短経路を見つけるのに、最適な方法でBFSを使用できますか？

答えて

関連する問題