簡介

• 在圖論中，最短路是十分重要的一部分，在很多問題中都有涉及

• 而現在所講的 SPFA 算法是十分優秀的算法，時間復雜度為 O(k?E)

• 其中 E 是圖的邊數，而 k 是一個常數，一般極小。

• 事實上 SPFA 就是在 Bellman-ford 算法的基礎上加上一個隊列優化，減少了冗余的松弛操作，是一種高效的最短路算法。

• 而且 SPFA 還能判負環，這種情況下類似 Dijkstra 算法等便沒有了用武之地！

用法

• 在隊列中進行，在點出隊入隊中更新值

• SPFA算法（BFS）模板如下：

void spfa_bfs(int st) {memset(dis,60,sizeof(dis));memset(bz,false,sizeof(bz));int l=0,r=1;dis[que[1]=st]=0;while(l<r){int now=que[++l];bz[now]=false;for(int i=first[now];i;i=next[i])if(dis[now]+w[i]<dis[en[i]]){dis[en[i]]=dis[now]+w[i];if(!bz[en[i]]) bz[que[++r]=en[i]]=true;}}return false; }

• 注釋：其中 que[] 為隊列，dis[] 為點到源點距離，l，r 分別左右指針，bz[] 為標志->點是否入隊。

• SPFA算法（DFS）模板如下：

void spfa_dfs(int x) {bz[x]=true;for(int i=first[x];i;i=next[i])if(dis[now]+w[i]<dis[en[i]]){dis[en[i]]=dis[now]+w[i];if(!bz[en[i]]]) spfa(en[i]);}bz[x]=false; }

判負環

• SPFA算法還有一個大優點是可以判負環

• 利用 SPFA 算法判斷負環有兩種方法：

• SPFA算法 的 dfs 形式，判斷條件是 存在一點在一條路徑上出現多次。
• SPFA算法 的 bfs 形式，判斷條件是 存在一點入隊次數大于總頂點數。

總結

• SPFA算法效率高，實用性強，是很有用的算法！

總結

以上是生活随笔為你收集整理的单源最短路 SPFA 算法模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。