ダイクストラのアルゴリズムは最短経路を生成しませんか？

Question

私はDijkstra's Algorithmを使って最短経路の問題に取り組んでいます。アルゴリズムが最短パスを提供するはずなので、私は問題を抱えていますが、アルゴリズムを実行した後、手で短絡してしまいます。これはちょうどこのアルゴリズムの副産物ですか？

私は生成しようとしているパスからである - > Zここで

は私が訪問した各頂点の最短距離のジャンプを取って、私はアルゴリズムを適用し得るパスです。

2 4 2 2 1 2 1 1 8  = 23 
a -> d -> g -> k -> r -> n -> q -> p -> t -> z 

私はこのパスを取る場合ので、これは私に混乱して：

4 2 2 2 2 2 2  = 16 
a -> c -> f -> i -> m -> p -> s -> z 

私は、アルゴリズムから生成された距離よりも5少ない距離を取得します。

私はどこかで踏み間違いましたか？

Answer 1

Dijkstraのアルゴリズムの仕組みを誤解しているようです。各ノードで最小の重みでエッジをとるのではなく、常に最初からの距離（ノード$ a $）を考慮する必要があります。検討中のすべての可能なパスのヒープを維持します。これは、エッジのない開始ノードとして開始し、各ステップで現在検討しているパスにノードの各出力エッジを追加して展開します。

あなたがどこに間違っていたかを要約しようとする言葉の不安です。私はDijkstraのアルゴリズムがどのように動作するかを再読することをお勧めします：http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm