7

ウィキペディアから取得した擬似コード： 

function Dijkstra(Graph, source):
 2      for each vertex v in Graph:                                // Initializations
 3          dist[v] := infinity ;                                  // Unknown distance function from source to v
 4          previous[v] := undefined ;                             // Previous node in optimal path from source
 5      end for ;
 6      dist[source] := 0 ;                                        // Distance from source to source
 7      Q := the set of all nodes in Graph ;                       // All nodes in the graph are unoptimized - thus are in Q
 8      while Q is not empty:                                      // The main loop
 9          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
10          if dist[u] = infinity:
11              break ;                                            // all remaining vertices are inaccessible from source
12          end if ;
13          remove u from Q ;
14          for each neighbor v of u:                              // where v has not yet been removed from Q.
15              alt := dist[u] + dist_between(u, v) ;
16              if alt < dist[v]:                                  // Relax (u,v,a)
17                  dist[v] := alt ;
18                  previous[v] := u ;
19                  decrease-key v in Q;                           // Reorder v in the Queue
20              end if ;
21          end for ;
22      end while ;
23      return dist[] ;
24  end Dijkstra.

ここで、14行目で、緩和がuまだ削除されていない隣接ノードにのみ適用されていることがわかりますQ。uしかし、から削除されたネイバーも取得すると、アルゴリズムは負の重みで機能Qするように見えます。この主張と矛盾する事例は見つかりませんでした。

では、なぜダイクストラのアルゴリズムがこのように変更されないのでしょうか。

4

6 に答える 6

13

ノードまたはエッジを2回トラバースしないようにするだけで、ダイクストラのアルゴリズムを負の値で機能させることができます。ここで、仕事とは、終了することを意味します。ただし、結果は最適ではない可能性があります。

ダイクストラのアルゴリズムには、貪欲な感覚があります。次のグラフを想像してみてください。

A --- 1 --- B
|           |
3          -4
|           |
C -- -1 --- D

AからBに移動する場合、最適なパスはACDBですが、ダイクストラのアルゴリズムはABを検出します。ダイクストラのアルゴリズムは欲張りアルゴリズムであるため、将来を予測させることはできません。将来を予測するということは、後でパスのコストが削減される可能性があることを知っているということです。これは、宛先が表示されるとすぐに終了するダイクストラのアルゴリズムのバージョンに適用された場合、変更が正しく機能しないことを意味することに注意してください。投稿したバージョンでは、ネガティブエッジを処理するためのより効率的な方法があることを除いて、変更は機能します（コメントを参照）。

ちなみに、負の値を持つ無向グラフや負のループを持つ有向グラフの最短経路は意味がありません。

于 2012-05-29T13:24:22.227 に答える
6

ダイクストラは、訪問する新しいノードを選択するときに、ルートからの最短パスを持つ非訪問ノードを選択するため、各ノードを1回だけ訪問する余裕があります。結果として、彼は、訪問していない別のノードを経由してそのノードに移動するより短い方法はないと安全に想定できます（AからBまでの最良の方法は2で、AからCまでの最良の方法は3であるため）。 A> C> Bなど、AからBへのより良い方法を見つける機会はありません。

負の重みを追加すると、突然この仮定が破られます。

もちろん、提案された変更を使用することもできますが、そうすると、各ノードに1回だけアクセスするメリットが失われます。したがって、Ford-Bellmanなどの他のアルゴリズムと比較してパフォーマンスの向上が失われます。

于 2012-05-29T13:44:45.433 に答える
4

基本的に2つのオプションがあります。

  1. 提案に応じてアルゴリズムを変更できます。負のサイクルのない有向グラフを使用している場合、これは正しいアルゴリズムですが、非常に遅くなる可能性があります（各ノードに何度もアクセスするため）。このアルゴリズムは指数関数的な時間計算量を持っている場合があると思います。

  2. ポテンシャルを使用してエッジコストを変更できます。すべての頂点には潜在的なh（v）があり、エッジu-> vの重みはw（u、v）+ h（u）-h（v）になります。これは、指定された2つの頂点（s、t）間のどちらのパスが最短であるかに影響せず、コストがh（s）-h（t）によって変更されるだけであることに注意してください。しかし、あなたは可能性を計算する必要があります。それを行う良い方法はここで提案されています：http：//en.wikipedia.org/wiki/Johnson's_algorithm

于 2012-05-29T13:55:47.757 に答える
3

いいえ、述べられているように不可能です。提供されたグラフタイプを厳しく制限しない限り、アルゴリズムは負の重みでは意味がありません。

ノードA、B、C、および重みAB = -1、BA = 0、BC=1のエッジを持つグラフを想定します。

現在、AとCの間の最短経路は存在しません。また、AとBの間をもう一度行き来することで、いつでもより短い経路を作成できます。

もちろん、アルゴリズムは引き続き実行されますが、間違った答えが返されます。

于 2012-05-29T13:20:55.707 に答える
2

はい、あなたの修正はあなたが言及していない2つの仮定の下で機能しますが、私は暗示されていると思います：

  1. 最短経路は、実際に入力グラフで定義する必要があります。非負の重みに関する制限を解除する場合は、少なくとも負の重みのサイクルがないことを要求する必要があります。
  2. 19行目の「decrease-keyvinQ」操作は、Qにないノードvでは実際には意味がありません。ただし、もちろん、新しい値を使用してそれらをQに再度追加できます。

ただし、ダイクストラアルゴリズムの重要な機能である最悪の場合の漸近的パフォーマンスが失われます。既製のダイクストラは、すべてのノードとすべてのエッジに最大で1回アクセスするため、優れたパフォーマンスを保証します。変更を含めると、すでに削除されているノードを優先キューに再度追加でき、グラフの大部分に何度もアクセスする必要がある場合があります。最悪の場合、たとえばベルマンフォードアルゴリズムと同じ数の緩和を実行する必要がありますが、優先キューの追加のオーバーヘッドがあります。これにより、最悪の場合のパフォーマンスがベルマンフォード法よりも悪くなります。したがって、負のエッジを持つグラフに適しています。

これは、変更したダイクストラが役に立たないという意味ではありません。負のエッジが非常に少ない場合、および/またはそれらの負のエッジが高価なパスによってグラフの残りの部分から分離されている場合は、ベルマンフォードよりもはるかに優れたパフォーマンスを発揮します。ただし、最悪の場合のパフォーマンスが非常に悪い場合に備えてください。

于 2014-11-19T19:48:42.530 に答える
1

さて、ダイクストラの修正バージョンですでにアクセスしたノードをリラックスするだけでは十分ではありません（そして、負のエッジを含むグラフで間違った答えを与えるでしょう）。さらに、リラックスしたエッジをコンテナに入れる必要があります（たとえば、優先キューまたは単にキュー）。したがって、19行目のコードを次のように修正できます。

if v is in priority queue
    then decrease-key(v)
else
    add v into priority queue

この場合、アルゴリズムが機能する可能性があります。さらに、ダイクストラの修正バージョンの効率は、正の重み付きグラフでは低下しません。これは当然貪欲アルゴリズムであるため、これは簡単に証明できます。

ただし、負のエッジを含むグラフの場合、新しいアルゴリズムは理論分析の観点からは遅くなる可能性がありますが、実際にはうまく機能します。

実際、中国のDingfan Duan（1994）によって公開されたSPFA（Shortest Path Faster Algorithm）という名前のアルゴリズムを見ることができます。多くのOIer（Olympic of Info）は、このアルゴリズムがダイクストラに勝る可能性があることを知っています。

于 2013-11-07T09:56:55.553 に答える