2

ダイクストラのアルゴリズムを使用して最短経路の問題に取り組んでいます。アルゴリズムが最短パスを提供することになっているため、問題が発生していますが、アルゴリズムを実行した後、手動で短縮パスを取得します。これは、このアルゴリズムの単なる副産物ですか?

生成しようとしているパスは 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 少ない距離が得られます。

私はどこかで道を間違えましたか？

4

1 に答える 1

3

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

それは、どこで間違ったのかを要約しようとする言葉の寄せ集めです。ダイクストラのアルゴリズムの仕組みを読み直すことをお勧めします: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

于 2012-04-20T23:01:55.247 に答える