圖論最短路徑算法——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不用說了吧。。。

判斷一個節點是否在隊列中，隻需要一個數組标記就好了。

具體代碼

#include <iostream>
#include <string.h>
#include <math.h>
#include <limits.h>
using namespace std;
struct _Way//定義_Way類型，表示某點與y點相連，長度為len 
{
    int y,len;  
};
int n,m;
int q;
_Way way[][] {};//way[i][j]标示i的第j條路 
_Way* bz[][] {};//輸入時用于判斷，有時輸入了重邊，肯定要取最小的，這個标記了這個邊的位址，友善判斷 
int now[] {};//now[i]即為節點i所連的邊的數量 Number of ways 
int dis[] {};//dis[i]即為從起點到i的最短距離 
int min(int a,int b){return a<b?a:b;}//取最小值函數 
void SPFA(int);
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=;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=;i<=n;i++)
    {
        if (dis[i]==INT_MAX) cout<<"-1"<<endl;//如果到不了輸出-1 
        else cout<<dis[i]<<endl;
    }
    return ;
}
void SPFA(int q)//q表示起點 
#define SIZE 2006
{
    bool bz[] {};//bz[i]表示i節點是否在隊列中 
    for(int i=;i<=n;i++)
        dis[i]=INT_MAX;//初始化為無限大 
    int head=,tail=;
    int d[SIZE+];
    dis[q]=;//起點到起點，當然為0了 
    d[]=q;
    bz[q]=;
    do
    {
        head++;
        if (head>SIZE) head=;//與下文一樣，用循環隊列 
        for(int i=;i<=now[d[head]];i++)//将跟它相連的邊都枚舉一遍 
        {
            tail++;
            if (tail>SIZE) tail=;
            d[tail]=way[d[head]][i].y;
            if (dis[d[tail]]<=dis[d[head]]+way[d[head]][i].len)//如果現在到那邊不比之前的優，則删掉它 
            {
                tail--;
                if (tail<) tail=SIZE;
                continue;
            }
            dis[d[tail]]=dis[d[head]]+way[d[head]][i].len;//更新 
            if (bz[d[tail]])
            {
                tail--;
                if (tail<) tail=SIZE;
                continue;
            }
            bz[d[tail]]=;//标記其以進入隊列 
        }
        bz[d[head]]=;//它出了隊列，将之前的1改為0 
    }
    while (head!=tail);
}
           

優化

C++者勿入