図論最短経路アルゴリズム——SPFA

あまり多くの人が被害を受けないように、私はやはりこのアルゴリズムを言って、それは実際には簡単ですが、人に回り道を言われました.
主な思想.
SPFAはBellman-Fordのキュー最適化だと言われています.このアルゴリズムは私も知っていますが、まだ試したことがありません.私はどんなアルゴリズムの最適化にかかわらず、どうせ私は似ていないように見えます.その考えは簡単です:BFS.これは似たようなもので、純粋なBFSではないと言われています.私はこれらを気にしないで、こんなに厳しく分けて何をしますか!開始点から、ノードのエッジを列挙し、それに接続されたすべてのパスを歩きます.他のノードを更新できるなら更新して、更新できないのか、直接キューから削除して、それを必要としないで、どうせそれは役に立たない.もう一つ、ノードがキューに入っているかどうかをマークし、ノードを追加するときは、キューに入っていないかどうかを見てみましょう.もしいるなら、入れなくてもいいです.どうせ無駄です.ある点がキューにN回現れたことがあれば,負のループに入り,無限小を付与すればよい.
説明の実装
まず図の記憶についてお話しします.この図は隣接行列で作られているわけではありません(あなたも使えますし、速度が遅くなり、オーバーフローなどの奇妙なエラーが発生するかもしれません).これは隣接表と呼ばれ、辺集配列と呼ばれる人もいます.つまり、各ノードが接続されているすべてのエッジを記録します.各エッジの情報には、この点の反対側と、このエッジの重みがあります.私はこのように定義しました

struct _Way//  _Way  ，     y   ，   len 
{
    int y,len;  
};
_Way way[1001][1001] {};//way[i][j]  i  j   
int now[1001] {};//now[i]    i        Number of ways 

もちろん、動的配列を開くこともできます.しかし、メモリを節約する必要がなければ、開けてください.しかし、私は試したことがありません.もっと煩わしいかもしれません.読み込み時には重辺を読み込んで、針で判断すれば良いのかもしれない正常なBFSは言うまでもないでしょう..1つのノードがキューにあるかどうかを判断するには、1つの配列タグだけが必要です.
具体コード

#include 
#include 
#include 
#include 
using namespace std;
struct _Way//  _Way  ，     y   ，   len 
{
    int y,len;  
};
int n,m;
int q;
_Way way[1001][1001] {};//way[i][j]  i  j   
_Way* bz[1001][1001] {};//       ，       ，       ，           ，     
int now[1001] {};//now[i]    i        Number of ways 
int dis[1001] {};//dis[i]      i      
int min(int a,int b){return a//       
void SPFA(int);
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,len;
        cin>>x>>y>>len;
        if (bz[x][y]!=NULL)//          
        {
            bz[x][y]->len=min(bz[x][y]->len,len);//          
            continue;
        }
        now[x]++;
        way[x][now[x]].y=y;
        way[x][now[x]].len=len;
        bz[x][y]=&(way[x][now[x]]);//       bz[x][y] 
    }
    cin>>q;
    SPFA(q);
    for(int i=1;i<=n;i++)
    {
        if (dis[i]==INT_MAX) cout<<"-1"<//       -1 
        else cout<return 0;
}
void SPFA(int q)//q     
#define SIZE 2006
{
    bool bz[1001] {};//bz[i]  i         
    for(int i=1;i<=n;i++)
        dis[i]=INT_MAX;//        
    int head=0,tail=1;
    int d[SIZE+1];
    dis[q]=0;//     ，   0  
    d[1]=q;
    bz[q]=1;
    do
    {
        head++;
        if (head>SIZE) head=1;//     ，      
        for(int i=1;i<=now[d[head]];i++)//             
        {
            tail++;
            if (tail>SIZE) tail=1;
            d[tail]=way[d[head]][i].y;
            if (dis[d[tail]]<=dis[d[head]]+way[d[head]][i].len)//             ，     
            {
                tail--;
                if (tail<1) tail=SIZE;
                continue;
            }
            dis[d[tail]]=dis[d[head]]+way[d[head]][i].len;//   
            if (bz[d[tail]])
            {
                tail--;
                if (tail<1) tail=SIZE;
                continue;
            }
            bz[d[tail]]=1;//         
        }
        bz[d[head]]=0;//     ，    1  0 
    }
    while (head!=tail);
}

最適化
C++者入るべからず
転載先:https://www.cnblogs.com/jz-597/p/11145319.html