SPFA算法讲解.ppt

SPFA算法;常见问题：;内容概要;SPFA 全称 Shortest Path Faster Algorithm 基本应用为快速求解单源最短路;Relax(u,v){ If F(v)F(u)+W_Cost(u,v) then F(v)=F(u)+W_Cost (u,v); };.......;SPFA则使用队列进行了优化！;在上图的例子中，每个节点只进队一次，只需N次运算。 相比Bellman-Ford优势明显。;但有负环时依然退化为O(NM);长期以来基于队列的SPFA并未取得突破 ;猜想;A1;S;让我们结合一道题目来进行探讨;苹果争夺战 两个人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：该算法结束时求得的解为正确解。;回顾思考过程，我们似乎感到： ;更新时需遍历所有相关节点 (本题算法); 三者的本质都是统一的，但随着算法的优化适用面逐步缩窄;总结;谢谢大家！