
今天分享一道有关 SPFA 单源最短路的算法题。
蒜头君在玩一个很好玩的游戏,这个游戏一共有至多 $100$ 个地图,其中地图 $1$ 是起点,房间 $n$ 是终点。有的地图是补给站,可以加 $k_i$ 点体力,而有的地图里存在怪物,需要消耗 $k_i$ 点体力,地图与地图之间存在一些单向通道链接。 蒜头君从 $1$ 号地图出发,有 $100$ 点初始体力。每进入一个地图的时候,需要扣除或者增加相应的体力值。这个过程持续到走到终点,或者体力值归零就会 Game Over。不过,他可以经过同个地图任意次,且每次都需要接受该地图的体力值。
输入格式
第 $1$ 行一个整数 $n$ ($n\leq 100$)。
第 $2$ ~ $n+1$ 行,每行第一个整数表示该地图体力值变化。接下来是从该房间能到达的房间名单,第一个整数表示房间数,后面是能到达的房间编号。
5 0 1 2 -60 1 3 -60 1 4 20 1 5 0 0
输出格式
若玩家能到达终点,输出 Yes
,否则输出 No
。
No
首先我们来看一下什么是 SPFA。
众所周知,Dijkstra 算法不能处理有负权的图,而 Bellman-ford 算法通过对图进行 $|V| – 1$ 次松弛操作,得到所有可能的最短路径,而 SPFA(Shortest Path Faster Algorithm)通常被认为是 Bellman-ford 算法的队列优化,在代码形式上接近于宽度优先搜索 BFS,是一个在实践中非常高效的单源最短路算法。
需要指出的是,SPFA 的本质是 Bellman-ford 算法的队列优化,由于 SPFA 没有改变 Bellaman-ford 的时间复杂度,国外一般来说不认为 SPFA 是一个新的算法,而仅仅是 Bellman-ford 的队列优化。
在一定程度上,可以认为 SPFA 是由 BFS 的思想转化而来:从不含边权或者说边权为 1 个单位长度的图上的 BFS,推广到带权图上,就得到了 SPFA。SPFA 与 BFS 的不同在于,BFS 中一个点出了队列就不可能重新进入队列,但是 SPFA 中一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本身被改进,于是再次用来改进其它的点,这样反复迭代下去。
SPFA 可以处理任意不含负环(负环是指总边权和为负数的环)的图的最短路,并能判断图中是否存在负环。
有了 BFS 的基础,我们很容易得到 SPFA 的算法描述:
d[i]
表示从源点 $s$ 到顶点 $i$ 的最短路,队列q
保存即将进行拓展的顶点列表,inq[i]
标识顶点 $i$ 是不是在队列中;- 初始队列中仅包含源点 $s$,且源点 $s$ 的
d[s] = 0
。 - 取出队列头顶点 $u$,扫描从顶点 $u$ 出发的每条边,设每条边的另一端为 $v$,边
<u,v>
权值为 $w$,若d[u] + w < d[v]
,则 将d[v]
修改为d[u] + w
,若 $v$ 不在队列中,则将 $v$ 入队。重复步骤直到队列为空。 - 最终
d[]
数组就是从源点出发到每个顶点的最短路距离。如果一个顶点从没有入队,则说明没有从源点到该顶点的路径。
void spfa(int s) { memset(inq, 0, sizeof(inq)); memset(d, 0x3f, sizeof(d)); d[s] = 0; inq[s] = true; queue<int> q; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = p[u]; i != -1; i = e[i].next) { int v = e[i].v; if (d[u] + e[i].w < d[v]) { d[v] = d[u] + e[i].w; if (!inq[v]) { q.push(v); inq[v] = true; } } } } }
在进行 SPFA 时,用一个数组 cnt[i]
来标记每个顶点入队次数。如果一个顶点入队次数 cnt[i]
大于顶点总数 $n$,则表示该图中包含负环。
很显然,SPFA 的空间复杂度为 $\mathcal{O}(V)$。如果顶点的平均入队次数为 $k$,则 SPFA 的时间复杂度为 $\mathcal{O}(kE)$,对于较为随机的稀疏图,根据经验 $k$ 一般不超过 $4$。
对于稀疏图而言,SPFA 相比堆优化的 Dijkstra 有很大的效率提升,但是对于稠密图而言,SPFA 最坏为 $\mathcal{O}(VE)$,远差于堆优化 Dijkstra 的 $\mathcal{O}((V+E)logV)$。
在看完了 SPFA 之后,这道题就比较容易了。
在套用 SPFA 模板的时候,注意要初始化 d[]
数组为负无穷大,并设置起点的体力值为 d[s] = 100
。
然后在 SPFA 的判断条件中 if (d[u] + e[i].w < d[v])
改成 if (d[u] + e[i].w > d[v])
因为我们需要保留体力最大的。
另外在每一个点入队以后,令 cnt[i]++
,若等于 $n$,说明有环,那么蒜头君就可以无限制地往这个点走,最终体力为无穷大,再也不需要考虑其他点的体力值了,因此一定可以走到终点。所以直接 return,并直接输出 Yes
。
最后的输出结果就是 d[n] > 0
。
#include <bits/stdc++.h> using namespace std; const int INF = 0x3F3F3F3F; const int MAX_N = 100; const int MAX_M = 10000; bool inq[MAX_N]; int d[MAX_N]; // 如果到顶点 i 的距离是 0x3F3F3F3F,则说明不存在源点到 i 的最短路 int cnt[MAX_N]; int n; struct edge { int v, next, w; } e[MAX_M]; int p[MAX_N], eid; void init() { memset(p, -1, sizeof(p)); eid = 0; } void insert(int u, int v, int w) { e[eid].v = v; e[eid].next = p[u]; e[eid].w = w; p[u] = eid++; } // SPFA 算法 void spfa(int s) { memset(inq, 0, sizeof(inq)); memset(d, -0x3F, sizeof(d)); // 套用模板,初始化为负无穷 memset(cnt, 0, sizeof(cnt)); // d[s] = 0; d[s] = 100; // 套用模板,初始体力是 100 inq[s] = true; queue<int> q; q.push(s); cnt[s]++; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = p[u]; i != -1; i = e[i].next) { int v = e[i].v; // if (d[u] + e[i].w < d[v]) { if (d[u] + e[i].w > d[v]) { // 套用模板,要保留走过去的时候生命值最大的 d[v] = d[u] + e[i].w; if (!inq[v]) { q.push(v); inq[v] = true; cnt[v]++; if (cnt[v] == n) { // 如果一个点入队 n 次,说明这个点能无限增加体力 // 置终点的剩余体力为无穷大 d[n] = INF; return; } } } } } } int main() { scanf("%d", &n); init(); // 本题 id 从 1 开始 for (int i = 1; i <= n; i++) { int hp, rooms, to; scanf("%d%d", &hp, &rooms); for (int j = 0; j < rooms; j++) { scanf("%d", &to); insert(i, to, hp); } } // 从起点开始做单源最短路 spfa(1); // 最终输出的结果是:达到终点的时候体力还大于 0 吗 printf("%s", d[n] > 0 ? "Yes" : "No"); }