自我分析,为什么用SPFA解差分方程,用最短路径求差分方程的最大解;用最长路径求差分方程的最小解.
如果给出的是一组:
a2 - a1 <= k1
a3 - a1 <= k2
....
之类的一组小于等于的不等式组...那么看 a - b <= k .. 化成 a < = b + k ... 这时构边是 b 为起点,a 为终点,权值为k的边...
而此时SPFA是求最短路径的Relax是
if ( d [ line.end ] > d [ line.start ] + line.wight )
d [ line.end ] = d [ line.start ] + line.wight;
那么 d [ line.end ] 的值最终将是 d [ line.start ] + line.wight 里最小的...若先令了一个源点...则这个d [ line.end ]就是 line.end 这个点的值..而这个值满足所有的约束条件..并且等于了最小的 a + k 但不会比最小的还要小..也就是 line.end 满足的是所有 line.end <= a+k 中a+k最小的...虽然line.end再小些也会满足与其所有 <= 的 关系..但正因为SPFA更新时一直是 = 所以求出的就是
d [ line.end ] 满足所有约束条件的最大值..
如果给出的是一组:
a2 - a1 >= k1
a3 - a1 >= k2
....
之类的一组小于等于的不等式组...那么看 a - b >= k .. 化成 a > = b + k ... 这时构边是 b 为起点,a 为终点,权值为k的边...
而此时SPFA是求最长路径,Relax是
if ( d [ line.end ] < d [ line.start ] + line.wight )
d [ line.end ] = d [ line.start ] + line.wight;
那么 d [ line.end ] 的值最终将是 d [ line.start ] + line.wight 里最大的...若先令了一个源点...则这个d [ line.end ]就是 line.end 这个点的值..而这个值满足所有的约束条件..并且等于了最大的 a + k 但不会比最大的还要大..也就是 line.end 满足的是所有 line.end >= a+k 中 a+k最大的...虽然line.end再大些也会满足与其所有 >= 的关系..但正因为SPFA更新时一直是 = 所以求出的就是
d [ line.end ] 满足所有约束条件的最小值..
分享到:
相关推荐
算法合集之《SPFA算法的优化及应用》.pdf
SPFA[知乎:叶枝黎曼].py
SPFA算法模版+邻接表实现.docx
SPFA算法的优化及应用.ppt
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
SPFA算法,acm常用的算法,求最短路径
自己打的spfa算法板子。包含邻接表的两种形式,邻接矩阵Map;此代码不完全,(使用是要注释掉部分的)在使用时要结合题意更改。望采纳!
基本思想 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。直到队列为空时算法结束;...松驰的结果是使j的d值减小
SPFA算法就解决了重复计算的问题,在大数据面前大大减少运行时间 该算法改善的思想是避免顶点进行无效的重复更新,对有待更新的顶点移入队列,已更新的顶点移出队列,避免待更新的顶点中存在重复顶点
最短路之SPFA算法.rar。。。算法复分析及例题设计,综合分析
SPFA算法 算法简介 简介.docx
SPFA算法实现,已经编译通过。。。。。。。。。
1 字符串处理 5 1.1 KMP . . . . . . . . ....1.2 e-KMP ....1.3 Manacher ....1.4 AC 自动机 ....1.5 后缀数组 ....1.5.1 DA ....1.5.2 DC3 ....1.6 后缀自动机 ....1.6.1 基本函数 ....1.6.2 例题 ....1.7 字符串 hash ....2.1 素数 ....
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 这个是自己写的,思想还是一样发的。
T005_最短路径SPFA算法,SPFA最短路径
这里面的内容是个PPT,介绍的很好,如果你想更加的清楚 SPFA 和Bellman_ford.ppt 最短路算法的原理,这是个不错的选择
SPFA算法优化及应用,SPFA算法优化及应用,SPFA算法优化及应用