最短回路SPFAアルゴリズム(隣接テーブルにより実現)

適用範囲:与えられた図には負の重みエッジが存在し、Dijkstraのようなアルゴリズムは武力を使う場所がなく、Bellman-Fordアルゴリズムの複雑さが高すぎて、SPFAアルゴリズムが役に立ちました.重み付け図Gには負の重み回路が存在しないこと,すなわち最短経路は必ず存在することを約束する.もちろん,このアルゴリズムを実行する前にトポロジーソートを行い,負の重みループが存在するか否かを判断することができるが,これは我々の議論の重点ではない.
主な考え方:図を隣接テーブルedges[mxan]で格納し、(もちろん隣接マトリクスでもいい)、その後SPFA操作を行い、dis[maxm]配列でソースポイントから他のポイントへの最短ルートを記録し、vis[maxm]配列でどの点が通過したかをマークし、que[maxm]キューで現在緩和すべき点を維持し、毎回先頭を取って操作する.キューが空になるまで、キューの先頭から拡張されたポイントが順番にキューの最後に追加されます.
実装方法:
キューを作成します.最初はキューに開始点しかありません.開始点からすべての点までの最短パスを記録するテーブルを作成します(テーブルの初期値は極大値に割り当てられ、そのポイントから彼自身のパスは0に割り当てられます).その後、リラックス操作を実行し、キューにある点を開始点としてすべての点の最短ルートにリフレッシュし、リフレッシュに成功し、リフレッシュされた点がキューにない場合は、その点をキューの最後に追加します.キューが空になるまで繰り返します.
負ループの有無判断:あるポイントがキューに入る回数がN回を超えると負ループが存在する(SPFAが負ループ付きの図を処理できない)
以下にコードを貼ります.

#include 

using namespace std;

#define INF 0x7fffffff

const int maxn = 100005;
const int maxm = 5005<<1;

struct Data{
    int x;
    int value;
    int next;
}edges[maxm];
int first[maxm], dis[maxm], que[maxm], vis[maxm];
int N, M;

void read_edges(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        first[i] = -1;
        vis[i] = 0;
        dis[i] = INF;
    }
    for(int e = 1, u, v, w; e <= M; e++){
        cin >> u >> v >> w;
        edges[e].x = v;
        edges[e].value = w;
        edges[e].next = first[u];
        first[u] = e;
    }
}

void SPFA(){
    int start = 1; //           ，      
    vis[start] = 1;
    dis[start] = 0;
    int head = 0, tail = 1, cur;
    que[tail] = start; //           
    while(head != tail){
        head = (head + 1) % 1000; //head                 
                                  //%1000       ，           
        cur = que[head];
        vis[cur] = 0; //               
        int k = first[cur]; //            ，            
        while(k != -1){
            if(dis[cur] > dis[edges[k].x] + edges[k].value) //     
                dis[cur] = dis[edges[k].x] + edges[k].value;
            if(!vis[edges[k].x]){
                vis[edges[k].x] = 1;
                tail = (tail + 1) % 1000;
                que[tail] = edges[k].x; //          
            }
            k = edges[k].next; //          
        }

    }
//  cout << dis[N] << endl; 
}

int main(){
    read_edges();
    SPFA();
    return 0;
}