Dijkstra 算法和广度优先搜索（BFS）都是解决图中单源最短路径问题的经典算法，但它们的适用场景、实现方式和性能特点有显著差异。以下是对 Dijkstra 算法与 BFS 的深度对比，结合 BFS 优化技巧，分析两者的原理、复杂度、适用场景、优缺点及实际应用，力求清晰且系统。一、算法概述1.1 BFS（广度优先搜索）原理：从起点开始，逐层（按距离递增）扩展节点，使用队列维护待访问节点，保证首次到达某节点时路径最短。核心思想：按层序遍历，适合无权图或边权均为 1 的图。数据结构：队列（queue 或 deque），访问标记（visited），距离数组（dist），可选前驱数组（prev）。适用场景：无权图、权值均为 1 的图、状态搜索（如迷宫、拼图）。1.2 Dijkstra 算法原理：从起点开始，基于贪心思想，每次选择当前未处理节点中距离最小的节点，更新其邻接节点的距离，直到所有节点处理完毕或到达终点。核心思想：优先扩展距离最小的节点，适合非负权图。数据结构：优先级队列（heapq 或最小堆），距离数组（dist），访问标记（可选），前驱数组（可选）。适用场景：带非负权图（如加权网络、地图导航）。二、核心对比特性BFSDijkstra适用图类型无权图或边权均为 1非负权图（边权可不同）核心数据结构队列（FIFO）优先级队列（最小堆）时间复杂度O(V + E)（V 为节点数，E 为边数）O((V + E) log V)（使用最小堆）空间复杂度O(V)（队列、距离数组、访问标记）O(V)（堆、距离数组）路径恢复通过前驱数组（prev）通过前驱数组（prev）是否保证最短路径是（无权图或权值均为 1）是（非负权图）处理负权边无法处理无法处理（需 Bellman-Ford 算法）实现复杂度简单，代码量少稍复杂，需维护优先级队列三、详细对比3.1 算法原理与流程BFS流程：起点入队，标记已访问，dist[start] = 0。出队当前节点 u，遍历其邻接节点 v。若 v 未访问，dist[v] = dist[u] + 1，v 入队，标记已访问。重复直到队列为空或到达终点。特点：