4

次の無向グラフのダイクストラの最短経路アルゴリズムを追跡しようとしています。

        (ロ)
       / \
      / \
  6/\9
    / \
   / \
  / \
 (A)- 5 -(C)- 1 -(F)----2----(I)
   \ /
    \ /
  4 \ / 2
      \ /
       \ /
        \ /
         (ニ)

明確にするために：
(N) はノードを表し、フォーマットのない数値は重みを表します。
A と C の間のエッジの重みは 5 です。
C と F の間のエッジの重みは 1 です。

ここで私のプロセスの概要を説明します。

A は最初のノードなので、アルゴリズムはここから始まります。D は安価なパスであるため、アルゴリズムは D にトラバースします。A は訪問済みとしてマークされます。つまり、再度トラバースすることはできません。

D では、F に移動することが容易にわかります。

Fは私が問題を抱え始めるところです。最短経路で C にたどり着くので、訪問した 2 つのノードの間で立ち往生し、I に到達する方法がありません。誰か助けてもらえますか?

編集: グラフの人については申し訳ありませんが、この質問はもともと電話から尋ねられました。できるだけ早く修正します。

4

4 に答える 4

5

あなたがそれに取り組んでいる方法は間違っています。「D では、F に移動することが容易にわかります」というのは正しくありません。最初に D にアクセスし、次に F ではなく C にアクセスします。アルゴリズムとその動作を注意深く見てください。

最初に A にアクセスすると、次のコストが発生します。B に 6、C に 5、D に 4、残りのノードは INFINITE です。

最初に D に移動します。ここでコストを更新して、A から F (D を通過) から 6 に移動します。次に訪問するノードは D ではなく、すべての未訪問ノードの中で最もコストが低い(5)ため、C です。ノード. A から C を通過して F に移動するコストは 6 です。これは既にあなたが持っているコストであるため、更新する必要はありません。

そこから、B と F の間には 6 の同点があります。最初に B に行くとしましょう。F への最短経路はすでに 6 であるため、何も起こりませんが、B を通過して F に行くには 15 のコストがかかります。これはより高価です。すでに持っているコストよりも低いため、コストを更新しないでください。次に、アクセスしていないすべてのノードの中で最もコストが低い F にアクセスします。そこからパスを I に更新すると、もう INFINITE ではなく 8 になります。

その結果、A から I への最短パスは次の順序になります: A - D - F - I .

于 2012-07-26T23:17:29.413 に答える
0

CからはまだAに戻ることができず、Fに戻ることもできないため、このパスはfalseです。行き止まりになる場合は、次の反復でグラフからCを削除するか、最後のステップを無視して、期待どおりにFからIに移動する必要があります。

于 2012-07-26T23:02:20.263 に答える
0

http://en.wikipedia.org/wiki/Dijkstraの s_algorithm - 別の頂点に移動する前に頂点のすべての隣接を処理することを覚えていますか? D に進む前に、C と B を処理します (それらの距離を計算します)。グラフから判断すると、D と F の間にルートはありません。

于 2012-07-26T23:03:49.817 に答える
0

Dijkstra のアルゴリズムは優先キューを使用します。これはグラフのウォークではなく、パスに似ていない順序で頂点を訪問することができます。たとえば、このツリーは次のとおりです。

A -> B -> C
  \
   > D -> E -> F

すべての重みで 1 が A、B、D、C、E、F の順に探索されます。反復ごとに、最小コストで頂点にアクセスしてポップします。最初に A をポップすると、B と D のコストが 1 に更新されます。B にアクセスすると、C のコストが 2 に更新されます。D を訪問すると、E のコストは 2 に更新されます。E にアクセスします。そして最後にF.

于 2012-07-26T23:11:22.890 に答える