2

Bellman-Ford のよりスマートなバージョンを以下に示します。

    //Queue Q; source s; vertices u, v
    Q ← s // Q holds vertices whose d(v) values have been updated recently.
    While (Q !empty)
    {

    u ← Dequeue(Q)

     for each neighbor v of u
     {
        Relax(u, v)
        if d(v) was updated by Relax and v not in Q
           Enqueue(v)
     }
   }

v = #vertices、E = #edges の場合、このアルゴリズムが (V*E) 時間の複雑さによって下限されるタイプのグラフを考えられる人はいますか?

これの落とし穴がどこにあるのか見てみたい。

4

3 に答える 3

3

ショートパスアルゴリズムについて最後に考えてから何年も経ちました。何かを忘れた場合は修正してください。

まず、負の加重サイクルの場合を除外することから始めますが、これは最悪の場合のパフォーマンスの原因となる可能性があります。

完全グラフにアクセスするとします。すべてのノードがsに隣接しているため、最初のノードからV-1ノードをキューに入れます。運が悪く、キューに入れる最後のノードがすべてのノードへの最短パスの一部であると仮定しましょう。結果として、V-2ノードをキューに入れる必要があります（ソースノードと評価しているノードを除いたすべてのノード...）。ここで、非常に不運なことになります。キューに入れる最後のノードが、残りのすべてのノードへのパスの一部であると仮定します...V-3ノードなどをキューに入れる必要があります。

したがって、すべてがうまくいかない場合は、V-1 * V-2 * ... * 3 * 2*1ノードを評価したことになります。これが|E|にどのように加算されるかを簡単に見つけることができます。

各ノードについて、何をしていますか？隣人のそれぞれをチェックします。各ノードにはV-1ネイバーがあります。

アルゴリズムの複雑さはすでにO（| V-1 | | E |）最悪の場合です。よく覚えていると思いますが、ベルマンフォードアルゴリズムは各エッジをチェックして、負の重みのサイクルがないことを確認します。これにより、V-1、別名（| V | | E |）の最悪の場合の複雑さに1が追加されます。

于 2012-05-21T13:29:52.313 に答える
0

これが機能するかどうかはわかりませんが、機能すると仮定すると、BFで改善が見られないケースを作成できます。開始ノードと終了ノードを作成し、その間に2つの頂点を接続するN個の頂点を配置します。アルゴリズムは、引き続きすべてのパスを考慮する必要があります。

于 2012-05-21T05:38:15.180 に答える
0

これは Ford-Bellman の改良です。通常よりも高速に実装されます。もちろん、最悪の場合、時間計算量は O(nm) になる可能性があります。しかし、このアルゴリズムをハックするための入力を作成するのは非常に困難です。コンテストでは、キューを使用した Ford-Bellman が Dijkstra よりも速く実行されます。ただし、配列呼び出し Inqueue を作成して、現在の要素がキューにあるかどうかを確認する必要があります。

qu : queue;
inqueue : array of bool;

for i in [1..n] do { d[i]=oo; inqueue[i]=false; }
qu.push(start);
d[start] = 0;

repeat
    u=qu.pop;
    inqueue[u]=false;
    for v in adj[u] do
    if minimize(d[v], d[u]+uv) then
    if !inqueue[v] then
    { inqueue[v] = true; qu.push(v); }
until qu.empty;
print d[target];
于 2013-09-03T08:52:10.090 に答える