在之前的Bellman-Ford算法中存在一个重复更新的问题，即每个枢纽点都要对全部顶点更新计算
SPFA算法就解决了重复计算的问题，在大数据面前大大减少运行时间
该算法改善的思想是避免顶点进行无效的重复更新，对有待更新的顶点移入队列，已更新的顶点移出队列，避免待更新的顶点中存在重复顶点
2021-12-22 20:40:49
14KB
1
基本思想
用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束；
利用了每个点不会更新次数太多的特点发明的此算法 ；
原理是著名的定理：
“三角形两边之和大于第三边”
在信息学中我们叫它三角不等式。
所谓对i,j进行松弛，就是判定是否d[j]>d[i]+w[i,j]，如果该式成立则将d[j]减小到d[i]+w[i,j]，否则不动。
d[i]：起点s到i的临时最短路长度
松驰的结果是使j的d值减小
2021-06-06 14:52:49
34KB
1