spfa讲义+前向星优化

SPFA 算算法法 求单源最短路的 SPFA 算法的全称是 Shortest Path Fast er Algorithm SPFA 算法是西南交通大学段凡丁于 1994 年发表的 从名字我们就可以看出 这种算法在效率上一定有过人之处 很多时候 给定的图存在负权边 这时类似Dijkstra 等算法 便没有了用武之地 而 Bellman Ford 算法的复杂度又过高 SP FA 算法便派上用场了 简洁起见 我们约定有向加权图 G 不存在负权回路 即 最 短路径一定存在 当然 我们可以在执行该算法前做一次拓扑排 序 以判断是否存在负权回路 但这不是我们讨论的重点 我们用数组 d 记录每个结点的最短路径估计值 而且用邻接 表来存储图 G 我们采取的方法是动态逼近法 设立一个先进先 出的队列用来保存待优化的结点 优化时每次取出队首结点u 并且用 u 点当前的最短路径估计值对离开 u 点所指向的结点 v 进行松弛操作 如果 v 点的最短路径估计值有所调整 且 v 点不 在当前的队列中 就将 v 点放入队尾 这样不断从队列中取出结 点来进行松弛操作 直至队列空为止 定理 只要最短路径存在 上述 SPFA 算法必定能求出最小 值 证明 每次将点放入队尾 都是经过松弛操作达到的 松 弛操作的原理是著名的定理 三角形两边之和大于第三边 在信 息学中我们叫它三角不等式 所谓对 i j 进行松弛 就是判定是否 d j d i w i j 如果该式成立则将 d j 减小到 d i w i j 否则不动 换言之 每次的优化将会有某个点 v 的最短路径估计值 d v 变 小 所以算法的执行会使 d 越来越小 由于我们假定图中不存在 负权回路 所以每个结点都有最短路径值 因此 算法不会无限 执行下去 随着 d 值的逐渐变小 直到到达最短路径值时 算法 结束 这时的最短路径估计值就是对应结点的最短路径值 证 毕 期望的时间复杂度 O ke 其中 k 为所有顶点进队的平均次 数 可以证明 k 一般小于等于 2 实现方法 建立一个队列 初始时队列里只有起始点 在建 立一个表格记录起始点到所有点的最短路径 该表格的初始值要 赋为极大值 该点到他本身的路径赋为 0 然后执行松弛操作 用队列里有的点去刷新起始点到所有点的最短路 如果刷新成 功且被刷新点不在队列中则把该点加入到队列最后 重复执行直 到队列为空 判断有无负环 如果某个点进入队列的次数超过N 次则存在 负环 SPFA 无法处理带负环的图 在一幅图中 我们仅仅知道结点 A 到结点 E 的最短路径长度 是 73 有时候意义不大 这附图如果是地图的模型的话 在算出 最短路径长度后 我们总要说明 怎么走 才算真正解决了问题 如何在计算过程中记录下来最短路径是怎么走的 并在最后将 它输出呢 Path 数组 Path i 表示从 S 到 i 的最短路径中 结点 i 之前 的结点的编号 注意 是 之前 不是 之后 最短路径算 法的核心思想成为 松弛 原理是三角形不等式 方法是上文 已经提及的 我们只需要在借助结点 u 对结点 v 进行松弛的同时 标记下 Path v u 记录的工作就完成了 SPFASPFA 算法采用图的存储结构是邻接表 方法是动态优化逼近法 算算法采用图的存储结构是邻接表 方法是动态优化逼近法 算 法中设立了一个先进先出的队列法中设立了一个先进先出的队列 Queue 用来保存待优化的顶点 优用来保存待优化的顶点 优 化时从此队列里顺序取出一个点化时从此队列里顺序取出一个点 w 并且用 并且用 w 点的当前路径点的当前路径 D W 去优化调整其它各点的路径值去优化调整其它各点的路径值 D j 若有调整 即 若有调整 即 D j 的值改小了 的值改小了 就将就将 J 点放入点放入 Queue 队列以待继续进一步优化 反复从队列以待继续进一步优化 反复从 Queue 队列队列 里取出点来对当前最短路径进行优化 直至队空不需要再优化为止 里取出点来对当前最短路径进行优化 直至队空不需要再优化为止 此时此时 D 数组里就保存了从源点到各点的最短路径值数组里就保存了从源点到各点的最短路径值 下面举一个实例来说明下面举一个实例来说明 SFFA 算法是怎样进行的 算法是怎样进行的 设有一个有向图设有一个有向图 G V E 其中 其中 V V0 V1 V2 V3 V4 E 2 10 3 7 4 5 6 见下图 见下图 算法执行时各步的算法执行时各步的 Queue 队的值和队的值和 D 数组的值由下表所示 数组的值由下表所示 表一表一 实例图实例图 SPFA 算法执行的步骤及结果算法执行的步骤及结果 初始第一步第二步第三步第四步第五步 que ue Dque ue Dque ue Dque ue Dque ue Dque ue D V00V10V40V20V300 V42V22222 5555 99 109999 算法执行到第五步后 队算法执行到第五步后 队 Queue 空 算法结束 源点空 算法结束 源点 V0 到到 V1 的的 最短路径为最短路径为 2 到 到 V2 的最短路径为的最短路径为 5 到 到 V3 的最短路径为的最短路径为 9 到 到 V4 的最短路径为的最短路径为 9 结果显然是正确的 结果显然是正确的 SPFA 在形式上和宽度优先搜索非常类似 不同的是宽度优先搜 索中一个点出了队列就不可能重新进入队列 但是 SPFA 中一个点 可能在出队列之后再次被放入队列 也就是一个点改进过其它的点 之后 过了一段时间可能本身被改进 于是再次用来改进其它的点 这样反复迭代下去 标标准准 SPFA 过过程程 以求某个结点 t 到某个结点 s 的最短路为例 稍加修改即为单源 最短路 Pascal 语语言言代代码码 const maxp 10000 最大结点数 var 变量定义 p c s t longint p 结点数 c 边数 s 起点 t 终点 a b array 1 maxp 0 maxp of longint a x y 存 x y 之间 边的权 b x c 存与 x 相连的第 c 个边的另一个结点 y d array 1 maxp of integer 队列 v array 1 maxp of boolean 是否入队的标记 dist array 1 maxp of longint 到起点的最短路 head tail longint 队首 队尾指针 procedure init var i x y z longint begin read p c for i 1 to c do begin readln x y z x y 一条边的两个结点 z 这条边的权值 inc b x 0 b x b x 0 y a x y z b x 0 以 x 为 一个结点的边的条数 inc b y 0 b y b y 0 x a y x z end readln s t 读入起点与终点 end procedure spfa s longint SPFA var i j now sum longint begin fillchar d sizeof d 0 fillchar v sizeof v false for j 1 to p do dist j maxlongint dist s 0 v s true d 1 s 队列的初始状态 s 为起点 head 1 tail 1 while headdist now a now b now i then begin dist b now i dist now a now b now i 修改最短路 if not v b now i then 扩展结点入队 begin inc tail d tail b now i v b now i true end end v now false 释放结点 一定要释放掉 因为这节点有 可能下次用来松弛其它节点 inc head 出队 end end procedure print begin writeln dist t end begin init spfa s print end 前前向向星星优优化化 星形 star 表示法的思想与邻接表表示法的思想有一定的相似 之处 对每个节点 它也是记录从该节点出发的所有弧 但它不是 采用单向链表而是采用一个单一的数组表示 也就是说 在该数组 中首先存放从节点 1 出发的所有弧 然后接着存放从节点 2 出发的 所有孤 依此类推 最后存放从节点 出发的所有孤 对每条弧 n 要依次存放其起点 终点 权的数值等有关信息 这实际上相当于 对所有弧给出了一个顺序和编号 只是从同一节点出发的弧的顺序 可以任意排列 此外 为了能够快速检索从每个节点出发的所有弧 我们一般还用一个数组记录每个节点出发的弧的起始地址 即弧的 编号 在这种表示法中 可以快速检索从每个节点出发的所有弧 这种星形表示法称为前向星形 forward star 表示法 例如 在例 7 所示的图中 仍然假设弧 1 2 l 3 2 4 3 2 4 3 4 5 5 3 和 5 4 上的权分别为 8 9 6 4 0 3 6 和 7 此时该网络图可以用前向星形表示法表 示如下 节点对应的出弧的起始地址编号数组 记为 point 节点号i123456 起始地址 ipoint134679 记录弧信息的数组 弧编号12345678 起点11234455 终点23423534 权89640367 在数组中 其元素个数比图的节点数多 1 即 且一point1 n 定有 对于节点 其对应的出弧存放1 1 point1 1 mnpointi 在弧信息数组的位置区间为 1 1 ipointipoint 如果 则节点 没有出弧 这种表示法与弧表表示 1 ipointipointi 法也非常相似 记录弧信息的数组 实际上相当于有序存放的 弧 表 只是在前向星形表示法中 弧被编号后有序存放 并增加一个 数组 记录每个节点出发的弧的起始编号 point for i 1 to m do readln a i b i e i qsort 1 m for i 1 to m do if f a i 0 then f a i i f n 1 m 1 for i n downto 1 do if f i 0 then f i f i 1 通常用在点的数目太多 或两点之间有多条弧的时候 一 般在别的数据结构不能使用的时候才考虑用前向星 除了不能直接 用起点终点定位以外 前向星几乎是完美的 前向星最常用的是来优化 spfa 最最基基本本的的前前项项性性优优化化的的 spfa 有有向向图图 var a b e array 1 1000 of longint vis array 1 2000 of boolean q d f array 1 2001 of longint n m i s t longint procedure qsort l r longint var i j x y longint begin i l j r x a l r shr 1 repeat while a i x do dec j if not i j then begin y a i a i a j a j y y b i b i b j b j y y e i e i e j e j y inc i dec j end until i j if i r then qsort i r if l j then qsort l j end procedure spfa s longint var i k l t longint begin fillchar vis sizeof vis 0 for i 1 to n do d i maxlongint d s 0 l 0 t 1 q 1 s vis s true repeat l l mod 10000 1 k q l for i f k to f k 1 1 do if d k e i d b i then begin d b i d k e i if not vis b i then begin t t mod 10000 1 q t b i vis b i true end end vis k false until l t end Begin readln n m for i 1 to m do readln a i b i e i qsort 1 m for i 1 to m do if f a i 0 then f a i i f n 1 m 1 for i n downto 1 do if f i 0 then f i f i 1 readln s t spfa s writeln d t end 例题例题 1 Sweet Butter 香甜的黄油 描述 农夫 John 发现做出全威斯康辛州最甜的黄油的方法 糖 把糖放在 一片牧场上 他知道 N 1 N 500 只奶牛会过来舔它 这样就 能做出能卖好价钱的超甜黄油 当然 他将付出额外的费用在奶牛 上 农夫 John 很狡猾 像以前的巴甫洛夫 他知道他可以训练这些奶牛 让它们在听到铃声时去一个特定的牧场 他打算将糖放在那里然后 下午发出铃声 以至他可以在晚上挤奶 农夫 John 知道每只奶牛都在各自喜欢的牧场 一个牧场不一定只有 一头牛 给出各头牛在的牧场和牧场间的路线 找出使所有牛到达 的路程和最短的牧场 他将把糖放在那 格式 PROGRAM NAME butter INPUT FORMAT file butter in 第一行 三个数 奶牛数 N 牧场数 P 2 P 800 牧场间道路 数 C 1 C 1450 第二行到第 N 1 行 1 到 N 头奶牛所在的牧场号 第 N 2 行到第 N C 1 行 每行有三个数 相连的牧场 A B 两 牧场间距离 D 1 D 255 当然 连接是双向的 OUTPUT FORMAT file butter out 一行 输出奶牛必须行走的最小的距离和 SAMPLE INPUT 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 programprogram butter butter varvar f1 f2 text f1 f2 text n p c longint n p c longint count array 1 800 ofcount array 1 800 of longint longint a b array 1 800 0 800 ofa b array 1 800 0 800 of longint longint d array 1 20000 d array 1 20000 ofof integer integer v array 1 800 v array 1 800 ofof boolean boolean dist array 1 800 dist array 1 800 ofof longint longint head tail longint head tail longint ans longint ans longint procedureprocedure init init varvar i j x y z longint i j x y z longint beginbegin assign f1 butter in reset f1 assign f1 butter in reset f1 assign f2 butter out rewrite f2 assign f2 butter out rewrite f2 readln f1 N P C readln f1 N P C fillchar count sizeof count 0 fillchar count sizeof count 0 forfor i 1i 1 toto n n dodo beginbegin read f1 x read f1 x inc count x inc count x end end forfor i 1i 1 toto p p dodo forfor j 1j 1 toto p p dodo a i j maxlongint a i j maxlongint forfor i 1i 1 toto c c dodo beginbegin read f1 x y z read f1 x y z inc b x 0 b x b x 0 y a x y z inc b x 0 b x b x 0 y a x y z inc b y 0 b y b y 0 x a y x z inc b y 0 b y b y 0 x a y x z end end end end procedureprocedure spfa s longint spfa s longint varvar i j now sum longint i j now sum longint beginbegin fillchar d sizeof d 0 fillchar d sizeof d 0 fillchar v sizeof v false fillchar v sizeof v false forfor i 1i 1 toto p p dodo dist i maxlongint dist i maxlongint dist s 0 v s true d 1 s dist s 0 v s t