能否将统计最短路径数的Dijkstra改进至O(V+E)时间复杂度？

先给结论：只有在特定类型的图里能做到，普通正权图下不可能。

1. 特殊图：无权/单位权图 #

如果你的图里所有边的权重都是1（或者全是无权边），那根本不用Dijkstra，直接用BFS就行，时间复杂度就是O(V+E)，还能顺便统计最短路径数量：

• 搞两个数组：dist存源点到每个节点的最短距离，count存到该节点的最短路径条数
• 初始化时，源点的dist设为0，count设为1
• 遍历队列里的节点时，对每个邻接节点：
  • 如果邻接节点的当前dist比「当前节点dist+1」大：更新它的dist，把count设成当前节点的count，然后把它放进队列
  • 如果邻接节点的dist刚好等于「当前节点dist+1」：直接把当前节点的count加到它的count里

这种场景下完全不需要Dijkstra的优先级队列，自然就能达到O(V+E)的效率。

2. 普通正权图：做不到O(V+E) #

对于边权可以是任意正数的图，目前理论上的下界就是Ω(E + V log V)——Dijkstra的核心逻辑是每次选出当前距离源点最近的节点来松弛，这个选节点的操作在最坏情况下绕不开对数级别的开销。哪怕你只是统计路径数量，也得先准确算出每个节点的最短距离，而距离计算依赖的优先级排序步骤没法省。

哪怕用斐波那契堆实现Dijkstra，也只能做到O(E + V log V)，这已经是理论最优了，没法再压到O(V+E)。

额外提一句路径计数的实现细节 #

不管用哪种Dijkstra的实现方式（数组、二叉堆、斐波那契堆），统计路径数量的逻辑都差不多：

• 当找到一条更短的路径到某个节点时，把该节点的路径数重置成前驱节点的路径数
• 当找到一条和当前最短路径长度一样的路径时，把前驱节点的路径数加到该节点的计数里
• 用二叉堆的话要注意，同一个节点可能多次进堆，遇到已经处理过的节点直接跳过就行

内容的提问来源于stack exchange，提问作者shiz