BFS与Dijkstra求解无加权图最短路径的渐近时间复杂度对比

核心结论 #

二者的渐近速度并不一致，题目中的推导只考虑了最宽松的上界对齐，存在多处遗漏的考量因素，实际所有场景下BFS的效率都优于斐波那契堆实现的Dijkstra算法，无权图场景下优先选择BFS计算最短路径。

具体遗漏的考量因素 #

• 复杂度紧界的差异
  题目中仅用了宽松的上界O(n log n)对齐二者复杂度，但BFS的时间复杂度是紧界Θ(n+m)，而斐波那契堆实现的Dijkstra时间复杂度是上界O(m + n log n)。题目仅给出m=O(n log n)的上界约束，没有说明m是Θ(n log n)的紧界：如果m是线性规模（比如m=Θ(n)的普通稀疏图），BFS的复杂度为Θ(n)，而Dijkstra的复杂度依然是O(n log n)，此时BFS渐近速度明显更快。
• 常数因子的巨大差异
  就算m恰好是Θ(n log n)，二者的大O上界量级相同，实际运行效率也有数量级差异：BFS仅依赖简单的队列入队、出队、邻接表遍历操作，常数因子极低；斐波那契堆的插入、减键、提取最小元等操作逻辑非常复杂，常数因子远高于BFS的基础操作，实际工程中几乎不会使用斐波那契堆实现Dijkstra，哪怕用二叉堆实现的Dijkstra运行效率也远低于同场景下的BFS。
• 算法设计的冗余开销
  BFS是专门针对无权图最短路径设计的算法，不存在多余的计算逻辑；Dijkstra是为带非负权的图设计的最短路径算法，用在无权图上时，会存在大量多余的权重比较、堆调整操作，本身就有设计层面的冗余开销。

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