Acwing1134

算法讲解：短路求方案数问题

问题描述

给定一个无向图，求从起点 $1$ 到每个节点的最短路径的方案数（即有多少条不同的路径可以到达该节点，且路径长度是最短的）。

关键点

1. 拓扑性：

   • 只有 BFS 和 Dijkstra 算法天然具备拓扑性（每次扩展节点时，路径一定是当前最短的）。
   • SPFA 不具备这种特性，因为队列中可能会重复处理某些节点，打破路径的拓扑顺序，导致结果错误。

2. 核心思想：

   • 在判断 dist[j] = dist[t] + w[i] 时，累计当前方案数。
   • 如果发现另一条到达同样距离的路径，继续累加方案数。

---

代码解析

1. 数据结构定义

const int N = 100010, M = 400010, mod = 100003;

int n, m;
int h[N], e[M], ne[M], idx; // 邻接表存储图
int dist[N], cnt[N]; // 最短路径距离 & 方案数

• 邻接表：
  • h[u]：节点 $u$ 的第一条边的索引。
  • e[idx]、ne[idx]：链式前向星存储目标节点和下一条边的索引。
• 路径属性：
  • dist[u]：从起点 $1$ 到节点 $u$ 的最短路径长度。
  • cnt[u]：从起点 $1$ 到节点 $u$ 的最短路径方案数。

---

2. 添加边

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

• 使用链式前向星添加边。
• 因为是无向图，每次输入需要调用两次 add，构建双向边。

---

3. BFS 算法

void bfs() {
    queue<int> q;
    q.push(1); // 从起点开始搜索
    memset(dist, 0x3f, sizeof dist); // 初始化所有点的距离为无穷大
    dist[1] = 0; // 起点的最短路径为 0
    cnt[1] = 1; // 起点的方案数为 1

while (q.size()) {
        int t = q.front(); // 当前节点
        q.pop();

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.push(j); // 入队
            } else if (dist[j] == dist[t] + 1) { // 找到同样短的路径
                cnt[j] = (cnt[j] + cnt[t]) % mod; // 累加方案数并取模
            }
        }
    }
}

关键点解析

1. 初始化：

   • 起点的 dist[1] = 0，cnt[1] = 1，表示从起点到起点只有一种方案。
   • 其他节点的 dist 初始化为无穷大，cnt 初始化为 0。

2. 松弛操作：

   • 如果发现更短路径 dist[j] > dist[t] + 1：
     • 更新目标节点的最短距离。
     • 当前节点的方案数继承给目标节点。
   • 如果发现同样短的路径 dist[j] == dist[t] + 1：
     • 累加当前节点的方案数。

3. 拓扑性：

   • BFS 确保了路径的拓扑顺序，先处理距离较短的节点。
   • 因此，每次更新 cnt[j] 时，已经保证了当前路径是最短路径。

---

4. 主函数

int main() {
    cin >> n >> m;

memset(h, -1, sizeof h); // 初始化邻接表

while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); // 添加双向边
    }

bfs();

for (int i = 1; i <= n; i++) cout << cnt[i] << endl; // 输出每个点的方案数
    return 0;
}

1. 输入图：

   • 使用邻接表存储无向图。
   • 每条边调用两次 add，分别加入两个方向。

2. 调用 BFS：

   • 计算从起点到每个节点的最短路径长度和方案数。

3. 输出：

   • 输出每个节点的方案数。

---

完整流程

1. 图的构建：
   • 使用邻接表存储无向图。
2. BFS 遍历：
   • 初始化起点的 dist 和 cnt。
   • 使用 BFS 依次处理每个节点，更新邻接节点的最短路径和方案数。
3. 输出方案数：
   • 遍历所有节点，输出到达该节点的方案数。

---

示例

输入：

4 4
1 2
2 3
3 4
1 3

输出：

1
2
2
2

解释：

• 从节点 $1$ 到节点 $3$ 有两条最短路径：$1\to 3$ 和 $1\to 2\to 3$。
• 从节点 $1$ 到节点 $4$ 有两条最短路径：$1\to 3\to 4$ 和 $1\to 2\to 3\to 4$。

---

时间复杂度

• 邻接表构建：$O(m)$。
• BFS 遍历：每条边最多被访问一次，时间复杂度 $O(m)$。
• 总复杂度：$O(m+n)$。

空间复杂度

• 邻接表存储边：$O(m)$。
• 距离和方案数组：$O(n)$。

---

优点与局限性

1. 优点：

   • BFS 自然适用于无权图，确保路径拓扑顺序。
   • 使用 cnt 数组可以高效统计路径方案数。
   • 通过 mod 防止数值溢出。

2. 局限性：

   • 仅适用于无权图或边权恒为 1 的场景。
   • 对于有权图，需要使用 Dijkstra 替代 BFS。

---

这段代码利用 BFS 的拓扑性，巧妙地解决了无权图中的最短路径方案数问题，并且结构清晰，易于扩展！