SPFA原则 pascal语言

如果从起点到点 i dist[i] 的距离从未更新过，则 dist[i] 没有更新连接点的价值。

相反，dist[i] 只有在更新了其他点时才有价值，并尽可能尝试更新。

这似乎是一种非常暴力的方法，但复杂性可以达到......O（v+E）。实际上，我不知道为什么复杂度如此之低......

程序核心：flag[st]=1; dist[st]=0;ST代表单个电源中电路最短的电源，这是起点。

而 （l<=r） 在队列不为空时执行。

更新连接到 d[l] edge[i] 的每个边 （i=......)relax(i);

d[l] 已更新，保留党旗[d[l]]=0; l=l+1;

子例程：procedure relax（k：longint）;

注意：k边的信息存储在s[k]（第k条边的开头），length[k]（长度），e[k]（结束）中。

if (dist[s[k]]+length[k]>=dist[e[k]])then exit;如果边没有更新值，请离开。

dist[s[k]]+length[k]:=dist[e[k]];更新边缘。

if （flag[e[k]]=false） 那么如果更新的点不在队列中，即我们不打算更新点 e[k]（但显然，经过这个放松操作，我们突然发现 e[k] 有被更新的值），那么将 e[k] 添加到队列中。

SPFA（Shortest Path Faster Algorithm）是一种单源最短路径算法，它不同于另一种单源最短路径算法Dijkstra（你对Dijkstra有什么不了解的？SPFA可用于处理负权重的图，也可以判断图中是否存在负加权循环。

事实上，SPFA 是 Bellman-Ford 算法的队列实现，可减少不必要的冗余计算。 SPFA的时间复杂度可以达到，k是每个节点进入团队的平均次数，k可以证明不超过2。

让我们先来谈谈我们都需要什么：

第 1 步：初始化

与 dijkstra 类似，您首先需要将 dist 数组中的每个元素初始化为 0x3f3f3f3f，我习惯于将其设置为 . 其次，将 visited 中的每个元素设置为 。 将源点的 dist 值设置为 0，并将 visited[ ] 设置为 。

第 2 步：加入团队

如果节点不在队列中，则更新节点的最短距离（即 dist 数组的值，如果 dist[ ]dist[ ] dist[ ] weight 是两个节点之间的权重，则更新节点的最短距离（即 dist 数组的值，如果 dist[ ]dist[ ] weight 是两个节点之间的权重），如果该数字大于节点总数，则记录每个节点排队的次数， 那么这意味着这个图中有一个循环。

第 3 步：重复第 2 步，直到队列为空

结束了，不是很容易吗？

Blue Bridge Cup 算法针对最短电路进行训练。

SPFA（Shortest Path Faster Algorithm）算法是一种寻找单一源最短路径的算法，它还具有判断负环的重要功能（这将反映在微分约束系统中），在Bellman-Ford算法的基础上增加了队列优化，减少了冗余松弛操作，是一种高效的最短路算法。