0

Bellman-Ford にわずかな変更を加えて、「役立つ」緩和のみを行うようにしました。つまり、d(v) が更新されたことを意味する緩和です。

define Relax(u, v):
 if d(v) > d(u) + w(u,v)         //w(u,v) = weight of edge u->v
    d(v) = d(u) + w(u,v)


INIT // our usual initialization.
Queue Q
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q not empty)
{
  u ← Frontof(Q);
  for each neighbor v of u
  {
    Relax(u, v)

    if d(v) was updated by Relax and v not in the Q  //Here's where we're a bit smarter
        ADD v to End of Q.                           //since we add to Q if 
                                                     //the relaxation changed d(v)
  }
}

ここで、すべての最短経路が最大で k 個の弧を持っているとします。このスマート バージョンでは k 個のアークしか通過しないため、最悪の場合の実行時間は O(V*k) です。|k| であるため、これは元の O(V*E) よりも少し高速です。< |E|

この改善されたバージョンが元の Bellman-Ford アルゴリズムより優れていないタイプのグラフを教えてください。つまり、最高のパフォーマンスは O(V*E) です。

4

1 に答える 1

0

すべてのエッジが負の重みを持つグラフを考えてみましょう。このグラフでは、頂点uが複数の入力エッジを持っている場合、頂点uはQに複数回追加されます。

ステートメント|k| <| E | は正しくありません：グラフに負のループがある場合、kは無限大です

于 2012-12-29T12:59:53.863 に答える