グラフィックアルゴリズムのSPFAアルゴリズム

1:アルゴリズムは単源の最短のSPFAアルゴリズムを求めることを説明して、1種の負の重みの辺を処理することができるアルゴリズムです.負の重みのあるエッジの場合、ディジェストラアルゴリズムは使用できませんが、bellman-fordは時間的に複雑です.簡潔にするため、重み付け図Gには負の重み回路が存在しない、すなわち最短経路が必ず存在することを約束する.もちろん,このアルゴリズムを実行する前にトポロジーソートを行い,負の重みループが存在するか否かを判断することができる.
二:アルゴリズム基本ステップのほとんどの最短パスアルゴリズムは以下の2つのステップである:1初期化2緩和操作
初期化:dis配列はすべてINFに割り当てられ、vis配列タグがキューにあるかどうか、最初はキューにノードがなく、すべてのvis配列要素がfalseに設定されています.キュー+緩和操作:キューヘッダ要素を読み出し、キューを出てvis配列値をfalseに変更します.点uに接続されたすべての点vを緩和操作し、推定値(すなわちd[v]を小さくする)を更新できれば更新し、また、点vがキューに存在しない場合は点vをエンキュー(マークを覚えておく)し、すでにキューに存在する場合はエンキューしない.(緩和されたノードは他のノードのdis値に影響を及ぼす可能性があるため、エンキューを継続する)
三:判断
負のループの有無を判断する:
あるポイントがキューに入る回数がN回を超えると負ループが存在する(SPFAは負ループ付きの図を処理できない)
広捜bfsとの違い:
SPFAは形式的には広さ(幅)優先探索と非常に類似しており、bfsの1つのポイントがキューを出ると再キューに入ることは不可能であるが、SPFAの1つのポイントがキューを出た後に再びキューに入れられる可能性があり、つまり1つのポイントが他のポイントを改善した後、一定時間が経過するとそれ自体が改善される可能性がある(
再入隊
)、そこで再び他の点を改善するために用いられ、このように繰り返していく.
最短パス自体はどのように出力しますか?
1つの図では、ノードAからノードEへの最短経路長だけが知られており、意味が大きくない場合がある.この図が地図のモデルであれば、最短経路の長さを算出した後、「どう行けばいいか」を説明してこそ、本当に問題が解決します.計算中に最短パスをどのように記録し、最後に出力するか.
ソース点sからiまでの最短距離において、ノードiより前のノードの番号(親ノード)を表すpath[i]配列を定義し、ノードuを介してノードvを緩和しながらpath[v]=uをマークすると、記録作業が完了する.
なぜDアルゴリズムは負のエッジが存在する場合に適用されないのですか?
どうして適用されないのですか?実は簡単に反例を見つけることができます.重み付け図を1枚仮定すると,ある辺の長さは負である.エッジ長が最小-10であると仮定すると,すべてのエッジ長に10を加えると,負の値のない重み付け図が得られる.このとき、Dijkstraアルゴリズムを用いて、ノードsからノードtまでの最短経路Lを算出し、Lはn辺を含み、総長はtである.では、原図では、エッジごとに10を減算するので、原図中のLの長さはt-10*nである.これはDiskstraアルゴリズムが算出した結果である.
問題は、10を加えた図について、sからtまでの経路Mが、長さt 1であり、Lよりも長いn 1辺を含むと仮定すると、復元後、各辺から10を減算する必要があり、Mの総長はt 1−10*n 1である.では、Mの総長はLの総長よりもっと長いのではないでしょうか.必ずしもそうとは限らない.n 1>nの場合、すなわち、Mの辺数がLの辺数よりも多く、Mの減算がLよりも多くなると、t 1−10*n 1
また、もっと簡単な例があります.もし1枚の図に総長が負数のリングがあれば、Dijkstraアルゴリズムはこのリングに沿ってずっと回り続け、地老天荒に回る可能性があります.の
四.コード#コード#

#include
#include 
#include 
#include 
using namespace std;

const int N = 2005;
int nodeNum , edgeNum;
int dis[N]; // d[i]    s i   
int c[N]; //             
bool vis[N];
const int INF = 0x3f3f3f3f;
bool loop; //       
int map[nodeNum][nodeNum];

void spfa(int start)
{
    //    ，   dis   vis  ，          
    queueq;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=nodeNum;i++)
        dis[i]=INF;
    dis[start]=0;
    q.push(start);
    vis[start]=true;

    //       ，        ，                 
    //       vis[],      ，    ，    
    while(!q.empty())
    {
        int temp = q.front();
        q.pop();
        vis[temp] = false;
        for(int i=1;i<=nodeNum;i++)
        {
            if(dis[temp] + map[temp][i] < dis[i])
            {
                dis[i] = dis[temp] + map[temp][i];
                if(!vis[i])
                {
                    q.push(i);
                    vis[i] = true;
                }
            }
        }
    }
}

五:最適化策略
1.SLFポリシー:参加するノードがjで、キューヘッダがiであり、dis[j]2.LLLポリシーは、キューのすべてのdisの平均値がxであるキューヘッダ要素を設定し、dis[i]>xの場合、iをキューの最後に挿入し、次の要素を検索してdis[i]<=xを見つけたことを知っていれば、キューを出て緩和操作を行う.