•最短パスのFloydアルゴリズム•最短パスのDijkstraアルゴリズム
Bellmanアルゴリズムの差はFloydアルゴリズムとDijkstraアルゴリズムの結合体ではない.

コアコード

// Bellman-Ford
dis[1] = 0;
for (int k = 1; k < n; k++)
    for (int i = 1; i <= m; i++)
        dis[v[i]] = min(dis[v[i]], dis[u[i]] + w[i]);

Bellmanアルゴリズムは隣接テーブルで図を格納する必要がある.u[i],v[i],w[i]はそれぞれi番目のエッジの始点,終点,重み値を表す.dis配列は、指定された頂点(ここでは1)から残りの各頂点への最短パスを表す.
上のコードの最後の行は、u[i]-->v[i]というエッジを通過して、1番の頂点からv[i]番の頂点までの距離を短くすることができるかどうかを示しています.すなわち、1番の頂点からu[i]番の頂点までの距離(dis[u[i])にu[i]-->v[i]というエッジ(重みw[i])を加えた値が、1番の頂点からv[i]番の頂点までの距離(dis[v[i])よりも小さいかどうかです.これはDijkstraアルゴリズムの「緩和」動作によく似ている.
また、Floydアルゴリズムを振り返ると、その三重ループk,i,jは、i番頂点が前のk頂点からj番頂点への最短経路を通過することを示す.Bellmanの二重ループk,iはこれと同様に,kラウンドを行って1番の頂点が最大k辺を通って残りの頂点に到達する最短経路を得ることを示す.
最短経路はループを含まないため,Bellmanアルゴリズムはn−1ラウンドまで緩和し,その後も緩和できればこの図に負の重みループが含まれていることを示す.従って、Bellmanアルゴリズムは、DijkstraおよびFloydよりも優れている点で、図中に負の重み回路が存在するかどうかを判断するために使用することができる.
負のループが存在するか否かを判断するには,n−1ラウンドをループした後に以下のコードを加えるだけでよい.

bool flag = false;
for  (int i = 1; i <= m; i++)
    if ( dis[v[i]] > dis[u[i]] + w[i] )
        flag = true;

このようにBellmanアルゴリズムの時間的複雑さはO(NM)であり,Dijkstraアルゴリズムよりも高い.しかし実際には多くの場合,Bellmanアルゴリズムはn−1ラウンドの緩和に達する前に最短経路を求め,その後のサイクルごとに緩和動作を行わないことが多い.従って、disが変化したか否かをブール変数でマークすることができ、変化がなければループから飛び出すことができる.

// Bellman-Ford
for (int k = 1; k < n; k++)
{
    bool check = false;
    for (int i = 1; i <= m; i++)
        if (dis[v[i]] > dis[u[i]] + w[i])
        {
            dis[v[i]] = dis[u[i]] + w[i];
            check = true;
        }
    if(!check)  break;
}

Bellmanアルゴリズムの流れを解析すると,ループの中で緩和が必要かどうかを判断するのに大きな時間が浪費されていることが分かった.しかし,緩和を実施するたびに,最短経路の計算が完了する頂点がいくつかあり,その後それらの値は変化しない.したがって,最短経路推定値のみが変化する頂点のすべてのエッジを毎回緩和することができる.

キュー最適化Bellmanアルゴリズム

その動作方法は、キューヘッダ頂点uを選択するたびに、頂点uの各エッジを緩和することである.リラックスに成功し、エッジの終点がキューにない場合は、頂点をキューに入れます.1つの頂点が同時にキューに現れるのは意味がないので、1つの配列bookで重みを判断することができます.頂点uのたるみが終わったら、uをチームから出します.このようにチームが空になるまで循環します.ここではチェーンテーブルを使う必要があります.配列でシミュレーションします.

コアコード

// Queue-optimized Bellman-Ford
/* 
   first[u[i]]    u[i]        ，next[i]  “   i  ” “    ”   
   q C++ STL      
*/
dis[1] = 0;
book[1] = 1;
q.push(1);
while(!q.empty())
{
    int cur = q.front();
    for (int k = first[cur]; k != -1; k = next[k])
        if (dis[v[k]] > dis[u[k]] + w[k])
        {
            dis[v[k]] = dis[u[k]] + w[k];
            if(!book[k])
            {
                book[k] = 1;
                q.push(k);
            }
        }
    book[cur] = 0;
    q.pop();
}

キュー最適化されたBellmanアルゴリズムは,形式的には広さ優先探索に似ているが,広さ検索時に1つの頂点がデキューされた後,通常は再エンキューされない点が異なる.1つの頂点がn回以上エンキューされると,この図に負のループがあると判断できる.キュー最適化Bellmanアルゴリズムの鍵は,前回緩和に成功した頂点だけがそれらに接続された頂点の最短経路推定値の変化を引き起こすことにある.