一篇文章 轻松搞懂 SPFA
目录
-
概念
-
BFM算法
-
- 松弛
- 初始化
- 时间复杂度
-
SPFA
-
- 进行优化
-
模板代码
-
- SPFA
- BFM算法
概念
SPFA （Shortest Path Faster Algorithm） 和 Dijkstra算法 可谓是 单源最短路 的两大双子星了。
SPFA 由前身 Bellman-Ford-Moore （Bellman-Ford或BFM）算法 添加一个 队列 来实现优化。
尽管如此，SPFA的复杂度最劣情况仍旧是BFM算法的复杂度，毕竟本质上只是多了一个优化的操作。
BFM算法
要知道，Richard Bellman （理查德.贝尔曼）是 动态规划 的创始人。
而BFM算法，正是运用了动态规划的思想。
相较于采用贪心思想的Dijkstra算法的无法处理 负权边 ，
动态规划显然没有这个限制。
松弛
那么状态是怎么转移 的呢？
我们记从源点 到每个节点i 的距离为 dis[i] （f[i]）。（dis=distance 距离）
对于已知的当前节点i 的的dis[i]，记其要转移的下一个节点j ，有边权w[i][j] 。（w=weight 权值）
那么显然有 dis[j] = min( dis[i]+w[i][j] , dis[j] ) 。
其实介个操作就叫 松弛 啦。
而且，当我们发现对于每个点都没法更优时，说明我们已经得到了最优解，
那么我们可以直接跳出，以优化时间。
初始化
由于我们需要的是最小值 ，
那么除了源点本身，其余都应该初始化为 +∞ 无穷大 （INF）
而源点本身到自己的距离自然是0 。
时间复杂度
显然我们需要枚举除了终点的每个 i 和 j，
故其 时间复杂度 大概为 节点数 N乘以边数M ，即 O（NM） 。
SPFA
进行优化
我们说过了，我们可以对BFM算法加入一个队列 来进行优化。
我们可以在松弛时，如果该点j可以使得当前路径更短 ，并且其不在队列中 ，再将其加入队列 。
因为，如果其已在队列中，我们对其再加入队列的访问是多余的 。
因为，如果后面可以继续使得路径更短，它就已经会被加入队列 。
所以，我们考虑加入一个 vis[i] 来表示其是否在队列中。（vis=visited 已访问）
所以对于该点，如果有负环 ，显然对其的访问次数会超过N （节点数）。
那么我们可以考虑加入一个count[i] ，统计每个点的访问次数，一旦超过N，说明该图存在负环。
显然，如果存在负环，那么最后最短路的结果会是负无穷 。。。
于是乎，对于存在负环时，我们使函数返回 0 。
模板代码
SPFA
这里大概打一下，不保证你copy过去能过。
模板还是自己打最好啦，大佬们的代码比我更好，毕竟你大佬还是你大佬。
bool SPFA(int start) 当图存在负环时，我们返回 0
{
memset(dis,127,sizeof(dis)); 初始化dis数组为最大值
dis[start]=0; 初始化时，源点与自身距离为 0
memset(vis,0, ,sizeof(vis)); 初始化vis数组为 0
vis[start]=true; 初始化时，源点入队并标记：标记
queue<int> Q; 储存访问节点的队列
Q.push(start); 初始化时，源点入队并标记：入队
while(!Q.empty()) 没有可访问节点时结束
{
int i=Q.front();Q.pop();
for(int j=1;j<=N;++j)
{
if(dis[j]>dis[i]+w[i][j]) 松弛
{
dis[j]=dis[i]+w[i][j];
if(!vis[j]) 未在队列中则加入，下次访问
{
vis[j]=true, 标记自身已入队
Q.push(j); 入队
if(++count[j]>N) return false; 计数，并检测负环
}
}
}
vis[i]=false; 出队时，删除入队标记
}
return true; 不存在负环，此时dis距离也已经处理好了
}
BFM算法
bool Bellman_Ford(int start) 同样有负环返回 0
{
memset(dis,127,sizeof dis);
dis[start]=0;
int u,v,w;
for(int i=1;i<N;++i) 对于每个点（除了终点，这里默认它为点n）
for(int j=1;j<=M;++j) 枚举每条边，这里的edges储存每条边的出、入、权
{
u=edges[j].u, v=edges[j].v, w=edges[j].w;
ij被for用了，我们用uv来代替下
dis[v]=max(dis[v],dis[v]>dis[u]+w);
}
bool pd=true; 判断是否含有负权回路。
如果我们最后已经理论上取得了最优解的情况下，发现还不够。
说明不是我们的问题，而是有负环。
for(int i=1;i<=M;++i)
if(dis[edges[i].v]>dis[edges[i].u]+edges[i].w)
{pd=false;break;}
return pd;
}