简介

• 在图论中，最短路是十分重要的一部分，在很多问题中都有涉及

• 而现在所讲的 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 算法模板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。