這篇文章來介紹一下spfa（Shortest Path Faster Algorithm）這種演算法 這是一種單源最短路的一種十分高效的的演算法。 我們需要用鄰接表來存儲一下圖，以及用隊列進行優化。 我們以1為起點，以n為終點來講一下（一共n個點） 用L數組記錄當前點的最短路 先把每一條邊的最短路賦成最 ...
這篇文章來介紹一下spfa（Shortest Path Faster Algorithm）這種演算法
這是一種單源最短路的一種十分高效的的演算法。
我們需要用鄰接表來存儲一下圖，以及用隊列進行優化。
我們以1為起點，以n為終點來講一下（一共n個點）
用L數組記錄當前點的最短路
先把每一條邊的最短路賦成最大值（賦多少自己決定，反正得大一點）
我們先把1入隊
因為我們用的是隊列進行優化，所以每次取出隊首元素s，對s所連接每一個點x進行如下操作
如果L[s]+s--x的長度比L[x]要短，那麼便更新L[x]，再判斷x是否已經入隊，若沒有入隊，則將x放入隊中（這裡需要註意一點，若x這個點入隊的次數已經超過了n次，那麼說明有負權環（spfa處理不了帶有負權環的圖），當然要是題目告訴了不存在負權環就不需要了）。
void add(int aa,int bb,int cc) { b[++cnt].v=bb;//當前點所連的邊 b[cnt].next=hh[aa];//上一條以當前點為起點的邊的序號 b[cnt].z=cc;//路的長度 hh[aa]=cnt;//鄰接表中最近的一條起點為當前點的邊的序號 } int main() { scanf("%d %d",&n,&m); for(i=1;i<=m;i++) { scanf("%d %d %d",&x,&y,&w);//起點，終點，長度 add(x,y,w);add(y,x,w);//鄰接表用來存邊，當然，如果是單向邊的話， // 就只做其中一個 } memset(l,0x3f,sizeof(l));//將每一條路的最短距離賦為最大值 l[1]=0;//起始點為點1，所以到點1的最短距離是0 x=1;//現在的x為起點，當然也可以是其它點 while(1) { if(h>t)break; j=hh[x]; while(1) { e=b[j].v; if(l[x]+b[j].z<l[e]){ l[e]=l[x]+b[j].z; p[e]=x; if(dd[e]==false)dd[e]=true,d[++t]=e;//dd數組記錄的是當前點是否在隊列中，如果不在就將其入隊； //dd判斷的是該點是否在隊中（所以可以用bool類型） } if(b[j].next==0)break;//如果鄰接表中在此之前沒有以當前點為起點的邊那麼就打斷迴圈 j=b[j].next; } dd[x]=false;//對當前點所連的所有點已經進行了鬆弛操作，那麼這個點就會出隊，那麼它的狀態便是不在隊中了 //如果題目中可能存在負環，那麼需要開一個數組記錄這個點的入隊次數，超過n次則證明存在負環 x=d[++h];//將x換為隊首元素 } //執行完以上代碼後，l[i]則代表的是起點到當前點的最短距離
