算法合集之《SPFA算法的优化及应用》.ppt

SPFA算法的优化与应用常见问题：内容概要SPFA全称ShortestPathFasterAlgorithm
基本应用为快速求解单源最短路Relax(u,v){
IfF(v)>F(u)+W_Cost(u,v)then
F(v)=F(u)+W_Cost(u,v);
}.......SPFA则使用队列进行了优化！在上图的例子中，每个节点只进队一次，只需N次运算。

相比Bellman-Ford优势明显。但有负环时依然退化为O(NM)长期以来基于队列的SPFA并未取得突破
猜想A1S让我们结合一道题目来进行探讨苹果争夺战
两个人A,B在一个5*6的矩阵里抢夺苹果。矩阵包含空地，4棵苹果树和障碍物，每个苹果树上有3个苹果。A先行动，然后两人轮流操作，每一回合每人可以向四周移动一格或停留在一棵苹果树下，如果苹果树非空可以摘下一个苹果。
两人不能移动到矩阵外，障碍物上或是对方的位置，且两人绝顶聪明。
问A最多可以抢到多少个苹果。问题分析:
经典的博弈模型，数据规模比较小，考虑动态规划但是….解决存在环的动态规划，常规思路:思路二：参考负权图上求最短路的思想两种常规解法都失败了，我们需要从新的角度来思考联想：SPFA在图论求最短路中的本质：同样：F[X,Y,K]=Max(G[X’,Y’,K’]+Apple)
是问题的终状态
G[X,Y,K]=Min(F[X’,Y’,K’])

一旦方程整体不成立便重赋值！
假设当前解为：
性质1：该算法结束时求得的解为正确解。回顾思考过程，我们似乎感到：
更新时需遍历所有相关节点(本题算法)三者的本质都是统一的，但随着算法的优化适用面逐步缩窄总结谢谢大家！
欢迎提问