题目描述
思路解析动画文字版
记住「更短覆盖、等长累加」这两条松弛规则,下面逐帧套它。
初始化:起点 0 的最短距离 dist[0]=0、最短路条数 ways[0]=1(到自己只有空路这一种)。其余点距离记 ∞、条数 0。把 (距离 0, 节点 0) 放进优先队列。终点是节点 4。
从队列取出距离最小的节点 0(距离 0)并定下来:它的最短距离 0、最短路条数 1 已确定。下面看它每条边,松弛邻居。
0-1(耗时 1):到 1 的新距离 = 0+1 = 1,比原来的 ∞ 更短。更新 dist[1]=1,条数整盘继承 ways[1]=ways[0]=1(旧路全作废),并入队。
0-2(耗时 1):到 2 的新距离 = 0+1 = 1,比原来的 ∞ 更短。更新 dist[2]=1,条数整盘继承 ways[2]=ways[0]=1(旧路全作废),并入队。
0-3(耗时 2):到 3 的新距离 = 0+2 = 2,比原来的 ∞ 更短。更新 dist[3]=2,条数整盘继承 ways[3]=ways[0]=1(旧路全作废),并入队。
从队列取出距离最小的节点 1(距离 1)并定下来:它的最短距离 1、最短路条数 1 已确定。下面看它每条边,松弛邻居。
1-0 这条边(耗时 1):邻居 0 已定下,跳过。
1-4(耗时 2):到 4 的新距离 = 1+2 = 3,比原来的 ∞ 更短。更新 dist[4]=3,条数整盘继承 ways[4]=ways[1]=1(旧路全作废),并入队。
从队列取出距离最小的节点 2(距离 1)并定下来:它的最短距离 1、最短路条数 1 已确定。下面看它每条边,松弛邻居。
2-0 这条边(耗时 1):邻居 0 已定下,跳过。
2-4(耗时 2):到 4 的新距离 = 1+2 = 3,恰好等于已有的 dist[4]=3。又发现一条同样短的路!条数累加 ways[4] = 1+ways[2](1) = 2。
从队列取出距离最小的节点 3(距离 2)并定下来:它的最短距离 2、最短路条数 1 已确定。下面看它每条边,松弛邻居。
3-0 这条边(耗时 2):邻居 0 已定下,跳过。
3-4(耗时 1):到 4 的新距离 = 2+1 = 3,恰好等于已有的 dist[4]=3。又发现一条同样短的路!条数累加 ways[4] = 2+ways[3](1) = 3。
从队列取出距离最小的节点 4(距离 3)并定下来:它的最短距离 3、最短路条数 3 已确定。下面看它每条边,松弛邻居。
4-1 这条边(耗时 2):邻居 1 已定下,跳过。
4-2 这条边(耗时 2):邻居 2 已定下,跳过。
4-3 这条边(耗时 1):邻居 3 已定下,跳过。
队列处理完毕。终点节点 4 的最短距离 = 3,最短路条数 ways[4] = 3。这 3 条最短路分别经 1、2、3 三个中转点(0→1→4、0→2→4、0→3→4),长度都恰为 3。
答案就是 ways[n−1] = ways[4] = 3(本题规模内未触发取模)。关键在松弛时分清「更短就覆盖条数、等长就累加条数」,Dijkstra 的逐点定值顺序保证每个点被定下时,它的条数已经把所有最短前驱都数齐了。
边界:单点 1;唯一路 1;同长两条累加成 2。
两个延伸:0 权要特判;可在最短路 DAG 上 DP 数路径。
参考代码
from typing import Listimport heapqclass Solution: def countPaths(self, n: int, roads: List[List[int]]) -> int: MOD = 10**9 + 7 g = [[] for _ in range(n)] for a, b, w in roads: g[a].append((b, w)); g[b].append((a, w)) dist = [10**30] * n ways = [0] * n dist[0] = 0; ways[0] = 1 heap = [(0, 0)] while heap: d, u = heapq.heappop(heap) if d != dist[u]: continue for v, w in g[u]: nd = d + w if nd < dist[v]: dist[v] = nd ways[v] = ways[u] heapq.heappush(heap, (nd, v)) elif nd == dist[v]: ways[v] = (ways[v] + ways[u]) % MOD return ways[n - 1]复杂度
- 时间：O((n+e)·log n)，e 条边,每条最多触发一次入堆,堆操作 O(log n);维护 ways 只是常数附加,整体仍是带堆 Dijkstra 的 O((n+e)log n)
- 空间：O(n+e)，邻接表 O(n+e),dist 与 ways 各 O(n),堆最坏 O(e),合计 O(n+e)
易错点
面试追问把动画讲成自己的话
追问如果边权可能为 0,这套计数还对吗?
追问能不能不用 Dijkstra,改成在最短路 DAG 上做 DP 数路径?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
从给定原材料中找到所有可以做出的菜
LeetCode 2115 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题