1

ダイクストラのアルゴリズムが負のエッジを持つ非巡回有向グラフで機能しない理由を理解できません。私が理解しているように、ダイクストラはグラフの幅優先トラバーサルを行い、適切なときにリラックスします。たとえば、次のグラフを考えてみましょう。

S->A (3)
S->B (4)
B->A (-2)

ここで、S はソース ノードです。これは私がそれが機能していると想像する方法です：

1) 距離 3 で A をマークします。距離 4 で B をマークします。

2) A を再帰します。A はノードを指していないので、何もしません。

3) B を再帰します。B は A を指しているので、B の距離 + B->A が A の現在の距離よりも小さいかどうかを確認します。2 < 3 なので、距離 2 で A をマークします。

しかし、私が使用している本は、ネガが機能しない理由を示すためにまさにこのグラフを示しているため、明らかにこれは機能する方法ではありません. 本の説明についていけない。ダイクストラはこのグラフをどのように処理するのでしょうか?また、なぜ彼らは私が想像している方法を使用しないのでしょうか?

4

1 に答える 1

4

問題は、ノードを処理すると、後でその距離を更新できないことです。これは、再帰的な更新が必要になり、すべてが台無しになるためです (読み取り: ノードが単調に増加する距離で処理されるというアルゴリズムの仮定に反して、ソース; それが必要な場所を確認するには、アルゴリズムの正確性の証明を参照してください)。したがって、A が処理されると、後でその距離を変更することはできません。つまり、以前に処理されたノードへの距離が短くなる可能性があるため、負のエッジを持つことはできません。距離が単調に増加するという仮定は、ノードが処理されたら黒くマークし、後で黒のノードを無視する理由です。そのグラフでは、A から S までの距離は 2 ですが、Dijkstra'

編集：ダイクストラのアルゴリズムが行うことは次のとおりです。

1) 距離 3 で A をマークし、処理待ちのノードのキューに入れます。B を距離 4 でマークし、キューに入れます。

2) A は先頭にいるので、キューから外します。A はノードを指していないため、距離を更新せず、キューに何も追加しないでください。A を処理済みとしてマークします。

3) B を待ち行列から外す。B は A を指していますが、A は処理済みとしてマークされています。エッジ B->A を無視します。B からの発信エッジはこれ以上ないので、これで完了です。

編集 2: DAG に関しては、Dijkstra のアルゴリズムはまったく必要ありません。DAG には常にトポロジー順序があり、これは O(|V| + |E|) で計算でき、距離d(w) = min {d(w); d(v) + c(v, w)}を更新するための規則として使用してトポロジー順序で頂点を処理します。エッジの長さは、O(|V| + |E|) で正しい距離を示します。全体として、それぞれ O(|V| + |E|) を必要とする 2 つのステップがあるため、任意のエッジ長を持つ DAG で単一ソースの最短パスを計算するのは全体的に複雑です。d(v)vc(v,w)(v,w)

于 2013-03-27T22:41:18.653 に答える