SPFA 求帶負權的單源最短路

int spfa_bfs(int s)
{
    ///s表示起點；
    queue  q;
    memset(d,0x3f,sizeof(d)); ///d數組中存下的就是最短路徑（存在的話）
    d[s] = 0;
    memset(c,0,sizeof(c));///c數組表示的是某一個節點的入隊次數
    memset(vis,0,sizeof(vis));///一如既往的標記數組

    q.push(s);  vis[s] = 1; c[s] = 1;
    ///頂點入隊vis要做標記，另外要統計頂點的入隊次數
    int OK = 1;///OK用來表示是否有最短路徑
    while(!q.empty())
    {
        int x;
        x = q.front(); q.pop();  vis[x]=0;
        ///隊頭元素出隊，並且消除標記
        for(int k = next[x]; k != -1; k = edge[k].next) ///遍歷頂點x的鄰接表
        {                                 ///但是我個人覺得這種表示鄰接表的方法不大好用
            int y = v[k];                   ///用vector g[maxn]; 應該更好理解
            if(d[x] + w[k] < d[y])
            {
                d[y] = d[x] + w[k];  ///松弛
                if(!vis[y])          ///頂點y不在隊內
                {
                    vis[y] = 1;      ///標記
                    c[y] ++;          ///統計次數
                    q.push(y);       ///入隊
                    if(c[y]>NN)      ///超過入隊次數上限，說明有負環
                        return OK=0;
                }
            }
        }
    }
    return OK;
}

這裡需要注意的是 在讀取邊的過程中，對邊的存儲方式 這將關系到你在遍歷與u相連的節點時 需要操作的內容

上面的存儲方式並不好，有更好的存邊方式，在這裡就直接介紹SPFA的使用方法，不再贅述了

在這裡給出一個鏈接 ，裡面有SPFA的更詳細的介紹和證明，以及SPFA的dfs實現，有興趣的同學可以進去看看~ ________SPFA鏈接biu~