1、SPFA 算 法 求 单 源 最 短 路 的 SPFA 算 法 的 全 称 是 ： Shortest Path Fast er Algorithm。 SPFA 算 法 是 西 南 交 通 大 学 段 凡 丁 于 1994 年 发 表 的 . 从 名 字 我 们 就 可 以 看 出 ， 这 种 算 法 在 效 率 上 一 定 有 过 人 之 处 。 很 多 时 候 ， 给 定 的 图 存 在 负 权 边 ， 这 时 类 似 Dijkstra 等 算 法 便 没 有 了 用 武 之 地 ， 而 Bellman-Ford 算 法 的 复 杂 度 又 过 高 ， SP FA 算 法 便 派 上 用 场
2、 了 。 简 洁 起 见 ， 我 们 约 定 有 向 加 权 图 G 不 存 在 负 权 回 路 ， 即 最 短 路 径 一 定 存 在 。 当 然 ， 我 们 可 以 在 执 行 该 算 法 前 做 一 次 拓 扑 排 序 ， 以 判 断 是 否 存 在 负 权 回 路 ， 但 这 不 是 我 们 讨 论 的 重 点 。 我 们 用 数 组 d 记 录 每 个 结 点 的 最 短 路 径 估 计 值 ， 而 且 用 邻 接 表 来 存 储 图 G。 我 们 采 取 的 方 法 是 动 态 逼 近 法 ： 设 立 一 个 先 进 先 出 的 队 列 用 来 保 存 待 优 化 的 结 点 ，
3、优 化 时 每 次 取 出 队 首 结 点 u， 并 且 用 u 点 当 前 的 最 短 路 径 估 计 值 对 离 开 u 点 所 指 向 的 结 点 v 进 行 松 弛 操 作 ， 如 果 v 点 的 最 短 路 径 估 计 值 有 所 调 整 ， 且 v 点 不 在 当 前 的 队 列 中 ， 就 将 v 点 放 入 队 尾 。 这 样 不 断 从 队 列 中 取 出 结 点 来 进 行 松 弛 操 作 ， 直 至 队 列 空 为 止 。 定 理 : 只 要 最 短 路 径 存 在 ， 上 述 SPFA 算 法 必 定 能 求 出 最 小 值 。 证 明 ： 每 次 将 点 放 入 队
4、尾 ， 都 是 经 过 松 弛 操 作 达 到 的 。 （ 松 弛操作的原理是著名的定理：“三角形两边之和大于第三边” ，在信 息学中我们叫它三角不等式。所谓对 i,j 进行松弛，就是判定是否 d jdi+wi,j，如果该式成立则将 dj减小到 di+wi,j，否则不动。 ）换 言 之 ， 每 次 的 优 化 将 会 有 某 个 点 v 的 最 短 路 径 估 计 值 dv变 小 。 所 以 算 法 的 执 行 会 使 d 越 来 越 小 。 由 于 我 们 假 定 图 中 不 存 在 负 权 回 路 ， 所 以 每 个 结 点 都 有 最 短 路 径 值 。 因 此 ， 算 法 不 会 无
5、限 执 行 下 去 ， 随 着 d 值 的 逐 渐 变 小 ， 直 到 到 达 最 短 路 径 值 时 ， 算 法 结 束 ， 这 时 的 最 短 路 径 估 计 值 就 是 对 应 结 点 的 最 短 路 径 值 。 （ 证 毕 ） 期 望 的 时 间 复 杂 度 O(ke)， 其 中 k 为 所 有 顶 点 进 队 的 平 均 次 数 ， 可 以 证 明 k 一 般 小 于 等 于 2。 实 现 方 法 ： 建 立 一 个 队 列 ， 初 始 时 队 列 里 只 有 起 始 点 ， 在 建 立 一 个 表 格 记 录 起 始 点 到 所 有 点 的 最 短 路 径 （ 该 表 格 的 初
6、始 值 要 赋 为 极 大 值 ， 该 点 到 他 本 身 的 路 径 赋 为 0） 。 然 后 执 行 松 弛 操 作 ， 用 队 列 里 有 的 点 去 刷 新 起 始 点 到 所 有 点 的 最 短 路 ， 如 果 刷 新 成 功 且 被 刷 新 点 不 在 队 列 中 则 把 该 点 加 入 到 队 列 最 后 。 重 复 执 行 直 到 队 列 为 空 判 断 有 无 负 环 ： 如 果 某 个 点 进 入 队 列 的 次 数 超 过 N 次 则 存 在 负 环 （ SPFA 无 法 处 理 带 负 环 的 图 ） 在 一 幅 图 中 ， 我 们 仅 仅 知 道 结 点 A 到 结
7、点 E 的 最 短 路 径 长 度 是 73， 有 时 候 意 义 不 大 。 这 附 图 如 果 是 地 图 的 模 型 的 话 ， 在 算 出 最 短 路 径 长 度 后 ， 我 们 总 要 说 明 “怎 么 走 ”才 算 真 正 解 决 了 问 题 。 如 何 在 计 算 过 程 中 记 录 下 来 最 短 路 径 是 怎 么 走 的 ， 并 在 最 后 将 它 输 出 呢 ？ Path数 组 ， Pathi表 示 从 S 到 i 的 最 短 路 径 中 ， 结 点 i 之 前 的 结 点 的 编 号 。 注 意 ， 是 “之 前 ”， 不 是 “之 后 ”。 最 短 路 径 算 法 的
8、 核 心 思 想 成 为 “松 弛 ”， 原 理 是 三 角 形 不 等 式 ， 方 法 是 上 文 已 经 提 及 的 。 我 们 只 需 要 在 借 助 结 点 u 对 结 点 v 进 行 松 弛 的 同 时 ， 标 记 下 Pathv = u， 记 录 的 工 作 就 完 成 了 。 SPFA 算法采用图的存储结构是邻接表，方法是动态优化逼近法。算 法中设立了一个先进先出的队列 Queue 用来保存待优化的顶点，优 化时从此队列里顺序取出一个点 w，并且用 w 点的当前路径 DW 去优化调整其它各点的路径值 Dj，若有调整，即 Dj的值改小了， 就将 J 点放入 Queue 队列以待继续
9、进一步优化。反复从 Queue 队列 里取出点来对当前最短路径进行优化，直至队空不需要再优化为止， 此时 D 数组里就保存了从源点到各点的最短路径值 。 下面举一个实例来说明 SFFA 算法是怎样进行的： 设有一个有向图 GV，E，其中，VV0,V1,V2,V3,V4 ， E ,2,10,3,7,4,5,6 ，见下图： 算法执行时各步的 Queue 队的值和 D 数组的值由下表所示。 表一 实例图 SPFA 算法执行的步骤及结果 初始 第一步 第二步 第三步 第四步 第五步 que ue D que ue D que ue D que ue D que ue D que ue D V0 0 V
10、1 0 V4 0 V2 0 V3 0 0 V4 2 V2 2 2 2 2 5 5 5 5 9 9 10 9 9 9 9 算法执行到第五步后，队 Queue 空，算法结束。源点 V0 到 V1 的 最短路径为 2，到 V2 的最短路径为 5，到 V3 的最短路径为 9，到 V4 的最短路径为 9，结果显然是正确的。 SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜 索中一个点出了队列就不可能重新进入队列，但是 SPFA 中一个点 可能在出队列之后再次被放入队列，也就是一个点改进过其它的点 之后，过了一段时间可能本身被改进，于是再次用来改进其它的点 ，这样反复迭代下去。 标 准 SPF
11、A 过 程 (以 求 某 个 结 点 t 到 某 个 结 点 s 的 最 短 路 为 例 ， 稍 加 修 改 即 为 单 源 最 短 路 ) Pascal 语 言 代 码 const maxp=10000; 最 大 结 点 数 var 变 量 定 义 p,c,s,t:longint; p,结 点 数 ;c,边 数 ;s:起 点 ;t:终 点 a,b:array1maxp,0maxp of longint; ax,y存 x,y 之 间 边 的 权 ;bx,c存 与 x 相 连 的 第 c 个 边 的 另 一 个 结 点 y d:array1maxp of integer; 队 列 v:array
12、1maxp of boolean; 是 否 入 队 的 标 记 dist:array1maxp 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(bx,0); bx,bx,0 := y; ax,y := z; bx,0： 以 x 为 一 个 结 点 的 边 的 条 数
13、 inc(by,0); by,by,0 := x; ay,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 distj:=maxlongint; dists:=0; vs:=true;d1:=s;队 列 的 初 始 状 态 ,s 为 起 点 head:=1;tail:= 1; while
14、 headdistnow+anow,bnow,i then begin distbnow,i:= distnow+anow,bnow,i; 修 改 最 短 路 if not vbnow,i then 扩 展 结 点 入 队 begin inc(tail); dtail := bnow,i; vbnow,i := true; end; end; vnow := false; 释 放 结 点 ， 一 定 要 释 放 掉 ， 因 为 这 节 点 有 可 能 下 次 用 来 松 弛 其 它 节 点 inc(head); 出 队 end; end; procedure print; begin writ
15、eln(distt); end; begin init; spfa(s); print; end. 前 向 星 优 化 星形（star）表示法的思想与邻接表表示法的思想有一定的相似 之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是 采用单向链表而是采用一个单一的数组表示。也就是说，在该数组 中首先存放从节点 1 出发的所有弧，然后接着存放从节点 2 出发的 所有孤，依此类推，最后存放从节点 出发的所有孤。对每条弧，n 要依次存放其起点、终点、权的数值等有关信息。这实际上相当于 对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序 可以任意排列。此外，为了能够快速检索从每个节点出
16、发的所有弧， 我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的 编号） 。在这种表示法中，可以快速检索从每个节点出发的所有弧， 这种星形表示法称为前向星形（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 节点号 i1 2 3 4 5 6 起始地址 )(pont1 3 4 6 7 9 记录弧信息
17、的数组 弧编号 1 2 3 4 5 6 7 8 起点 1 1 2 3 4 4 5 5 终点 2 3 4 2 3 5 3 4 权 8 9 6 4 0 3 6 7 在数组 中，其元素个数比图的节点数多 1（即 ） ，且一point n 定有 ， 。对于节点 ，其对应的出弧存放1)(it 1)(mi 在弧信息数组的位置区间为 ，)(),(ipontit 如果 ，则节点 没有出弧。这种表示法与弧表表示1poini 法也非常相似， “记录弧信息的数组”实际上相当于有序存放的“弧 表” 。只是在前向星形表示法中，弧被编号后有序存放，并增加一个 数组（ ）记录每个节点出发的弧的起始编号。point for
18、i:=1 to m do readln(ai,bi,ei); qsort(1,m); for i:=1 to m do if fai=0 then fai:=i; fn+1:=m+1; for i:=n downto 1 do if fi=0 then fi:=fi+1; 通常用在点的数目太多，或两点之间有多条弧的时候。一 般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接 用起点终点定位以外，前向星几乎是完美的。 前向星最常用的是来优化 spfa 最 基 本 的 前 项 性 优 化 的 spfa(有 向 图 ) var a,b,e:array11000 of longint; vis
19、:array12000 of boolean; q,d,f:array12001 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 aix do dec(j); if not(ij) then begin y:=ai; ai:=aj; aj:=y; y:=bi; bi:=bj; bj:=y; y:=ei; ei:=ej; ej:=y; inc(i); dec(j); end; until ij; if isum then ans:=sum; end; procedure main; var i:longint; begin ans:=maxlongint; for i:=1 to p do spfa(i); end; begin init; main; writeln(f2,ans); close(f2); end.
