データ構造体グラフ

Question

重み付け有向非循環グラフ（DAG）Gと頂点sを指定すると、最大ヒープを持つDijkstraアルゴリズムは、sからグラフの他のすべての頂点までの最長経路の重みを計算します。 それは本当ですか？

Answer 1

ダイクストラのアルゴリズムは、次のグラフのために動作しません：

ノードは、次の順序（s = 1）で分析されますノード4ため

nodes = [1, 3, 4, 2] 

distance[1] = 0 
distance[3] = 4 
distance[4] = 7 
distance[2] = 2 

最長距離は9あります7の代わりに。