1134 最短路计数（单源最短路径扩展-最短路计数）

分手后的思念是犯贱 2022-09-16 13:28 201阅读 0赞

**1. 问题描述：**

给出一个 N 个顶点 M 条边的无向无权图，顶点编号为 1 到 N。问从顶点 1 开始，到其他每个点的最短路有几条。

**输入格式**

第一行包含 2 个正整数 N，M，为图的顶点数与边数。接下来 M 行，每行两个正整数 x，y，表示有一条顶点 x 连向顶点 y 的边，请注意可能有自环与重边。

**输出格式**

输出 N 行，每行一个非负整数，第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路，由于答案有可能会很大，你只需要输出对 100003 取模后的结果即可。如果无法到达顶点 i 则输出 0。

**数据范围**

1 ≤ N ≤ 10 ^ 5，  
1 ≤ M ≤ 2 × 10 ^ 5

**输入样例：**

5 7  
1 2  
1 3  
2 4  
3 4  
2 3  
4 5  
4 5

**输出样例：**

1  
1  
1  
2  
4  
来源：[https://www.acwing.com/problem/content/description/1136/][https_www.acwing.com_problem_content_description_1136]

**2. 思路分析：**

分析题目可以知道我们需要求解**最优方案的数目**，可以先回忆一下之前的dp问题是如何求解最优方案数目的，对于当前的状态f\[i\]，我们不重不漏地将f\[i\]划分为若干个子集，分别求解出每一个子集等于全局最小值的个数，使用cnt\[i\]表示状态i可以取到的方案数目，在最短路中也是类似的；我们可以使用dis\[i\]表示所有从起点到i的路径长度的最小值，cnt\[i\]表示从起点到i的最短路径的条数（dis数组只能够记录路径的最小值，所以需要使用一个额外的数目来记录路径条数），我们可以根据最后一条边的方向划分为若干个集合，这样划分的子集能够保证是不重不漏的，但是需要注意的一个问题是划分为这些子集之后，这些子集的结果是可以直接计算出结果的，也即满足**拓扑序**的要求；对于求解最短路径的条数，需要引入一个概念--最短路径拓扑图，这个图中保存的是每一个点是由哪一个点更新过来的，本质上是一棵树（树一定满足拓扑序的要求--不存在环），我们需要保证在求解最短路径条数的时候是在最短路径拓扑图上求解的那么就可以保证答案一定是正确的；求解最短路径的算法一般有三个系列：① bfs，一般求解权重只有0或者1的图；② dijkstra最短路径算法；③ Bellman-ford，spfa算法（spfa其实是优化版的Bellman-ford算法）；我们在使用这些算法求解最短路径条数的时候需要注意一下能否在求解最短路径的时候维护最短路径的条数；对于bfs，每一次对于当前弹出来的队首元素，都是往四周扩展一圈，而且先搜到的点离起点的距离肯定是最短的，所以每一个点只会入队和出队一次，也即每一个点只会被更新一次，满足拓扑序的要求；对于② dijkstra算法不管是朴素版还是优化版，都可以保证每一个点只会被更新一次，也满足拓扑序的要求，第①②种算法因为每一个点都会被更新一次所以满足拓扑序的要求，所以可以在求解最短路径的过程中维护最短路径的条数，直接求解没有问题；但是对于第③种spfa算法则不可以了，因为每一个点可能会入队和出队多次，不能够保证拓扑序的要求，所以spfa算法在求解最短路径的时候不能够直接维护最短路径的条数，但是就不能够使用spfa求解最短路径的条数了吗，其实是可以求求解的，具体的做法是先跑一边spfa求解出最短路径的数值，求解完之后再枚举w\[i\]，把最短路径拓扑图建出来，然后再求解最短路径条数即可；并且对于求解最短路径条数的问题，一般边权都不会是0，因为边权是0那么路径条数就变成无穷条了，对于这道题目来说因为是无向边，并且权重为1所以直接使用bfs解决即可，在bfs的过程中使用cnt\[i\]维护到i这个点的最短路径条数即可，主要分为两种情况更新：

*  dis\[next\] > dis\[p\] + 1，此时需要dis和cnt，dis\[next\] = dis\[p\] + 1，cnt\[next\] = cnt\[p\]
 *  dis\[next\] = dis\[next\] + 1，此时只需更新cnt，cnt\[i\] += cnt\[p\]，说明存在另外一个边的方向使得到达next这个点的权重是相等的，路径条数累加即可

可以参照[背包问题求解方案数目][Link 1]的题目，这两道题的本质是一样的。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    import collections
    
    
    class Solution:
        def bfs(self, n: int, g: List[List[int]]):
            mod = 100003
            INF = 10 ** 10
            dis = [INF] * (n + 1)
            dis[1] = 0
            cnt = [0] * (n + 1)
            # 第一个起点的方案数目为1
            cnt[1] = 1
            # 因为是bfs所以需要借助双端队列
            q = collections.deque([1])
            while q:
                # 弹出队头元素
                p = q.popleft()
                for next in g[p]:
                    # 主要是分为两种情况更新dis和维护cnt
                    if dis[next] > dis[p] + 1:
                        # 更新最短距离和和路径条数
                        cnt[next] = cnt[p] % mod
                        dis[next] = dis[p] + 1
                        q.append(next)
                    elif dis[next] == dis[p] + 1:
                        cnt[next] = (cnt[next] + cnt[p]) % mod
            return cnt
    
        def process(self):
            n, m = map(int, input().split())
            g = [list() for i in range(n + 1)]
            for i in range(m):
                x, y = map(int, input().split())
                # 双向边
                g[x].append(y)
                g[y].append(x)
            cnt = self.bfs(n, g)
            for i in range(1, n + 1):
                print(cnt[i])
    
    
    if __name__ == "__main__":
        Solution().process()

[https_www.acwing.com_problem_content_description_1136]: https://www.acwing.com/problem/content/description/1136/
[Link 1]: https://blog.csdn.net/qq_39445165/article/details/120309730
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5b455de316554759a83f4d2e1124849c.png