首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >计蒜客 - 闯关游戏 | SPFA

计蒜客 - 闯关游戏 | SPFA

作者头像
凝神长老
发布2020-04-16 15:12:17
4260
发布2020-04-16 15:12:17
举报

今天分享一道有关 SPFA 单源最短路的算法题。

蒜头君在玩一个很好玩的游戏,这个游戏一共有至多 个地图,其中地图 是起点,房间 是终点。有的地图是补给站,可以加 点体力,而有的地图里存在怪物,需要消耗 点体力,地图与地图之间存在一些单向通道链接。蒜头君从 号地图出发,有 点初始体力。每进入一个地图的时候,需要扣除或者增加相应的体力值。这个过程持续到走到终点,或者体力值归零就会 Game Over。不过,他可以经过同个地图任意次,且每次都需要接受该地图的体力值。

输入格式

第 行一个整数 ()。

第 ~ 行,每行第一个整数表示该地图体力值变化。接下来是从该房间能到达的房间名单,第一个整数表示房间数,后面是能到达的房间编号。

5
0 1 2
-60 1 3
-60 1 4
20 1 5
0 0

输出格式

若玩家能到达终点,输出 Yes,否则输出 No

No

首先我们来看一下什么是 SPFA。

众所周知,Dijkstra 算法不能处理有负权的图,而 Bellman-ford 算法通过对图进行 次松弛操作,得到所有可能的最短路径,而 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 的算法描述:

  1. d[i] 表示从源点 到顶点 的最短路,队列 q 保存即将进行拓展的顶点列表,inq[i] 标识顶点 是不是在队列中;
  2. 初始队列中仅包含源点 ,且源点 的 d[s] = 0
  3. 取出队列头顶点 ,扫描从顶点 出发的每条边,设每条边的另一端为 ,边 <u,v> 权值为 ,若 d[u] + w < d[v],则 将 d[v] 修改为 d[u] + w,若 不在队列中,则将 入队。重复步骤直到队列为空。
  4. 最终 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] 大于顶点总数 ,则表示该图中包含负环。

很显然,SPFA 的空间复杂度为 。如果顶点的平均入队次数为 ,则 SPFA 的时间复杂度为 ,对于较为随机的稀疏图,根据经验 一般不超过 。

对于稀疏图而言,SPFA 相比堆优化的 Dijkstra 有很大的效率提升,但是对于稠密图而言,SPFA 最坏为 ,远差于堆优化 Dijkstra 的 。

在看完了 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]++,若等于 ,说明有环,那么蒜头君就可以无限制地往这个点走,最终体力为无穷大,再也不需要考虑其他点的体力值了,因此一定可以走到终点。所以直接 return,并直接输出 Yes

最后的输出结果就是 d[n] > 0

完整代码参见:https://www.jxtxzzw.com/archives/5265

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-04-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 凝神长老和他的朋友们 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档