国赛讲题现场↑
咳咳
正经点写篇科普（顺便复习一遍orz）
简单来讲，就是在图里从 一个点 到其他任意一点的一种玄学算法
并且它可以处理负权边qwq
还能判断负权环
哇哇哇是不是很棒？
至于时间复杂度嘛……
这就是它的玄学所在，我们稍后再细细道来w。
void spfa( ) { memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); queue<int> q;//#include<queue> q.push(1); d[1]=0; v[1]=1; while( q.size() ) //while( !q.empty() ) { int x,y; x=q.front();
q.pop();
v[x]=0; for(int i=head[x] ; i ; i=next[i])//链式前向星 if( f[ y=to[i] ] > f[x] + val[ i ]) { f[y]=f[x]+val[i]; if(v[y]==0) q.push(y); v[y]=1; } } }
在这个算法的提出者段凡丁的论文中，他证明的时间复杂度是O(kE)，k是小常数
但是（划重点）
(以后再更新吧，时间不够了w)
原文：https://www.cnblogs.com/H2SO4/p/10391798.html