algorithm - 最短経路グラフ

Question

有向グラフ G 、重み、s ソース頂点、およびグラフ内の各頂点の d[v] (s から v までの距離) が与えられた場合、最短パス グラフを構築するアルゴリズムを見つける必要があります。

BFS でエッジを処理することを考えていましたが、どのエッジがツリー内にあるべきか、および各頂点の d[v] が true であることを確認する方法をどのように知ることができますか。

Answer 1

ダイクストラを実行します。{u、v}を接続するエッジeにd [u] + w [e] = d [v]というプロパティがある場合、そのエッジは探しているツリーの一部です。

このように、実際にはツリーになっていない可能性がありますが、MSTには探しているプロパティがあります

Answer 2

BFS アルゴリズムは、特定のルート ノードと他のすべてのノードの間の最短パスを、重み付けされていないグラフ (またはすべての重みが同じ) に対してのみ見つけるのに役立ちます。各エッジの重みが異なる場合は、ダイクストラ アルゴリズムが適しています。ただし、グラフに負の重みがある場合、ダイクストラ アルゴリズムは機能しません。負の重みがある場合は、Bellman ford アルゴリズムを使用する必要があります。