Dijkstraのアルゴリズムは最短経路を生成しないか？ - アルゴリズム、グラフ理論、最短経路、ダイクストラ

私は最短経路問題を通して働いていますこのアルゴリズムは最短パスを提供するはずなので問題を抱えていますが、このアルゴリズムを実行した後は手でショートパスが発生します。これは単なるこのアルゴリズムの副産物ですか？

私が生成しようとしているパスはaからです - > 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小さい距離が得られます。

どこかでミスしましたか？

回答：

あなたがダイクストラの考えを誤解しているように見えるアルゴリズムは動作します。各ノードで最小の重みを持つエッジを取得するのではなく、常に先頭からの合計距離（ノード$ a $）を考慮する必要があります。考慮中のすべての可能なパスのヒープを維持します。これはエッジのない開始ノードとして始まり、各ステップで現在検討しているパスにノードの各出エッジを追加してすべてのパスを追加することによって拡張します。

それはあなたが間違ったところを要約しようとしている単語の寄せ集めです。私はDijkstraのアルゴリズムがどのように機能するかを再読することを提案します： http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm