每周一算法：最短路计数

题目描述

给出一个$N$个顶点 $M$ 条边的无向无权图，顶点编号为 $1$ 到 $N$。

问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。

接下来 $M$ 行，每行两个正整数 $x,y$，表示有一条顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。

输出格式

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

如果无法到达顶点 $i$ 则输出 $0$。

样例 #1

样例输入 #1

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
1
2
3
4
5
6
7
8

样例输出 #1

1
1
1
2
4
1
2
3
4
5

提示

【数据范围】
$1\le N\le 10^5$,
$1\le M\le 2\times 10^5$

算法思想

根据题目描述，求从起点 $1$ 到每个顶点有多少条不同的最短路，即求最短路的方案数。可以使用动态规划的思想，定义状态$f[i]$表示起点到顶点$i$的最短路的方案数。

要在图中计算状态，需要先构造出图的拓扑序列。但是题目中给出的是无向无权图，通过测试样例可以看出，图中有可能存在环，如下图所示，因此不一定存在拓扑序列，因此不能通过循环迭代直接计算状态。

由于求的是最短路的方案数，考虑能否使用最短路算法，在计算最短路的同时将状态计算出来。要使用最短路计算方案数需要要满足不能存在代价为$0$的环，否则经过该环的最短路的方案数为无穷大。而题目中题目给出的是无向无权图，可以认为边权都为$1$，因此不存在代价为$0$的环。

那么有哪些最短路算法可以进行状态计算呢？

题目求的是起点到其余顶点的最短路，那么可以选择的最短路算法有：BFS、Dijkstra、Bellman-Ford（SPFA）等，是不是这些算法都可以用来计算状态呢？要计算$i$点的状态，必须保证$i$阶段所依赖的状态都已经被计算出来，也就是说在计算最短路时，能够找到一个拓扑序来计算状态。这样就需要最短路算法能够构造出一个最短路拓扑图。如下图所示：

而对于下列算法：

• BFS算法计算（边权相同的）最短路时，是一层一层进行扩展的，每个点只会入队$1$次，出队$1$次，进队和出队都是满足拓扑序的。
• Dijkstra算法计算最短路时，每个点只会出队$1$次，当一个点出队时，是不会更新前面已经出队的点到起点的最短路，因此出队序列也满足拓扑序。
• Bellman-Ford（SPFA）算法计算最短路时，每个点可以入队出队多次，当一个点出队时可能会更新之前出队的点的最短路，这样就不能保证出队序列具备拓扑序。

也就是说， BFS和 Dijkstra算法在求最短路过程中可以进行状态计算。

算法流程

• 将起点$1$的最短路径方案数初始化为$1$，即$f[1]=1$
• 在求解最短路的过程中
  • 当$v$点到起点的最短路能够被$u$点松弛，即$dis[v]>dis[u]+1$，则到$v$的最短路方案数等于到$u$点的最短路方案数，即$f[v]=f[u]$
  • 当$v$点到起点的最短路等于经过$u$点中转的距离，则需要累加到$u$点的最短路方案数，即$f[v]=f[v]+f[u]$

代码实现

#include 
//注意：边数为200000，无向图需要建双向边，所以边的总数为400010
const int N = 100010, M = 400010, mod = 100003;
int n, m;
int h[N], e[M], ne[M], idx;
//dist[i]表示从1号点到i号点的最短距离
//f[i]表示从1到点到i号点的最短距离的路径数
int dis[N], f[N], q[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs()
{
    memset(dis, 0x3f, sizeof dis);
    //注意，到1号点的最短路径数初始为1
    dis[1] = 0, f[1] = 1;
    //bfs每个点只会入队一次，使用普通队列即可
    int hh = 0, tt = 0;
    q[0] = 1;
    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            //可以更新最短距离
            if(dis[v] > dis[u] + 1)
            {
                dis[v] = dis[u] + 1;
                q[++ tt] = v;
                //此时的路径数不变
                f[v] = f[u];
            }   
            else if(dis[v] == dis[u] + 1)//如果最短距离相等，累加最短路径数
            {
                f[v] = (f[v] + f[u]) % mod;
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
       
        add(a, b), add(b, a);  //无向图，双向边
    }
    bfs();
    for(int i = 1; i <= n; i++) printf("%d\n", f[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57