SPFA算法.ppt

SPFA算法 广东中山纪念中学 姜碧野 * * 常见问题： 1、在负权图上判断是否存在负环 2、解决有环的动态规划转移方程 这些问题该如何解决？ 内容概要 第一部分 简要介绍SPFA的基本实现 第二部分 提出SPFA一种新的实现方式 第三部分 介绍如何灵活使用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的核心正是松弛操作： ....... A1 T An S 但松弛操作直接得出的Bellman-Ford算法效率低下 For Time=1 to N For (u,v)∈E Relax(u,v) 上图数据中，总运算量高达N^2 而边(S, A1)虽然被调用N次。 但实际有用的只有一次 SPFA则使用队列进行了优化！ 思想： 只保存被更新但未扩展的节点。 减少了大量无用的计算，效率大大提高！ A1 A2 ……. A4 An-1 A3 An Head Tail 当前待扩展元素 在上图的例子中，每个节点只进队一次，只需N次运算。 相比Bellman-Ford优势明显。 ....... A1 T An S 但有负环时依然退化为O(NM) 在1000000个点，2000000条边的随机数据中 SPFA甚至比使用堆优化的Dijkstra还要快。 A1 T An S ……. 长期以来基于队列的SPFA并未取得突破 传统的队列实现: 缺点：NewNode需要之前的元素全部出队后才能扩展 中断了迭代的连续性 猜想： 能否把NewNode放在Head后面进行下一次扩展？ A1 A2 ……. A4 An-1 A3 An Head Tail New Node 猜想 程序 图论中的基本算法 ：深度优先有哪些信誉好的足球投注网站 基本数据结构：栈 SPFA_Dfs(Node) { For (Node,v) ∈E If dis[v] dis[Node]+w(Node,v) then dis[v]=dis[Node]+w(Node,v); SPFA_Dfs (v); } } 核心思想: 每次从刚刚被更新的节点 开始递归进行下一次迭代！ 后进先出！ 判断存在负环的条件： 重新经过某个在 当前有哪些信誉好的足球投注网站栈中的节点 A1 T An S ……. 相比队列，深度优先有着先天优势： 在环上走一圈，回到已遍历过 的点即有负环。 绝大多数情况下时间为O(M)级别。 实战:WordRings (ACM-ICPC Centrual European2005) 676个点，100000条边，查找负环。 DFS只需219ms！ 一个简洁的数据结构和算法 在一定程度上解决了大问题。 S A1 A2 Ak Ak-1 …...... B1 ……. B2 Bm T +∞ 最坏情况下需要KM次运算 优化：随机调整边的顺序 则期望k+mLogk 还有不足吗？ 让我们结合一道题目来进行探讨 最短路问题其实只是SPFA迭代思想在图论 中的一个特例，在其他各类动态规划，迭代法解 方程，不等式等问题中往往也能发挥奇效！ 苹果争夺战 两个人A,B在一个5*6的矩阵里抢夺苹果。矩阵包含空地，4棵苹果树和障碍物，每个苹果树上有3个苹果。A先行动，然后两人轮流操作，每一回合每人可以向四周移动一格或停留在一棵苹果树下，如果苹果树非空可以摘下一个苹果。 两人不能移动到矩阵外，障碍物上或是对方的位置，且两人绝顶聪明。 问A最多可以抢到多少个苹果。 此时B不能再向左移动 而A可以逐步摘下3棵树的所有苹果 开始时A无法移动 之后B一直不动， A无法得到任何苹果 问题分析: 经典的博弈模型，数据规模比较小，考虑动态规划 F[X,Y,K]表示轮到A行动， A的位置为X，B的位置为Y， 苹果树状态为K(使用状态压缩的4位4进制表示）时 A最多获得多少苹果。 G[X,Y,K]类似表示轮到B行动时，A最少获得的苹果数。 状态数为30*30*256*2 ≈500000 可以承受 转移方程也简单，直接