最短路求方案数

整体思路：

  • 首先引入拓扑序的概念：计算当前状态时，当前状态所依赖的状态都已经计算出来了
  • 类似DP，先求出全局最小值，再分别求出每个子集中等于全局最小值的元素数量，和最短路的唯一区别是，DP是在拓扑图中做最短路，但普通的最短路中可能存在环
  • 若将最短路的模型转化为拓扑图，则可以用类似DP的方式处理求方案数的问题
  • 其次引入最短路树（最短路拓扑图）
    • 概念：记录每个点是由哪个点更新来的，即若 dist[j] = dist[t] + w[i] (t -> j)，j 可由 t 更新而来。
    • 如果没有任何限制，则可能存在权值为0的环，可以在此环上转无限次，则最短路径的方案数为 INF，相当于无解了，求不出确切的树。
    • 所以，如果想要求最短路的方案数，则图中不能存在权值为0的环，依照上述方案记录路径，即可形成拓扑图，简单地说，将可以求最短路时可以被利用的边保存（可更新最短路径上的点的边保存），其余边去掉。

分析算法：

求最短路的算法系列：

热知识：判断是否满足拓扑序，此点不能更新之前已更新的点，反之则形成环，非拓扑序

  • BFS系列（bfs）
    • 一层一层扩展，保证每个点只入队一次，且只出队一次，满足拓扑序
  • Dijkstra系列（朴素dijkstra，堆优化dijkstra，双端队列广搜）
    • 每个点只作为最小值出队一次，之前出现的点的距离一定小于等于该点的距离，所以此点一定不会更新之前的点，满足拓扑序
  • Bellman-ford系列（Bellman-ford，spfa）
    • 按照边更新，一个点出队都无法确定其为最小值，每个点可能入队多次，本身不具备拓扑序，若使用则需先用spfa算法预处理出来最短路径，建立最短路径树，然后在最短路径树上跑bfs等算法。

总结：bfs系列和dijkstra系列算法可以直接做，spfa比较麻烦需要预处理。

代码如下：

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
void bfs()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0, cnt[1] = 1;
    
    int hh = 0, tt = -1;
    q[ ++ tt ] = 1;
    
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                q[ ++ tt] = j;
            }
            else if(dist[j] == dist[t] + 1)
                cnt[j] = (cnt[j] + cnt[t]) % mod;
        }
    }
}