BFS、Dijkstra 与 Floyd 最短路径算法对比

核心对比

算法	主要用途	适用情况	不适用情况	时间复杂度
BFS	无权图的单源最短路径	无权图、等权图	一般带权图	邻接表： $O(V+E)$ ；邻接矩阵： $O(V^2)$
Dijkstra	非负权图的单源最短路径	所有边权 $\ge 0$	有负权边	邻接矩阵： $O(V^2)$ ；堆优化： $O((V+E)\log V)$
Floyd	所有顶点对之间的最短路径	可有负权边，但不能有负权回路	负权回路	$O(V^3)$

其中， $V$ 表示顶点数， $E$ 表示边数。

BFS 最适合求解无权图的单源最短路径。

      B
     / \
A --    D
     \ /
      C

从 $A$ 出发时，BFS 会逐层搜索：

A\rightarrow\{B,C\}\rightarrow D

因为无权图默认每条边的长度都是 $1$ ，所以：

\boxed{\text{最短路径}=\text{经过边数最少}}

如果各边权值分别为 $2,5,10$ 等不同数值，一般不能使用 BFS 求最短路径。

使用邻接表时，每个顶点最多访问一次，每条边最多检查一次或两次，因此：

\boxed{O(V+E)}

使用邻接矩阵时，需要扫描矩阵中的顶点关系，时间复杂度为 $O(V^2)$ 。

Dijkstra 最适合求解非负权图的单源最短路径。例如从 $A$ 出发：

A --2-- B
|       |
5       1
|       |
C --1-- D

它可以分别求出 $A\rightarrow B$ 、 $A\rightarrow C$ 和 $A\rightarrow D$ 的最短距离。

重点： Dijkstra 不能处理负权边。

例如：

A\xrightarrow{2}B,\qquad A\xrightarrow{5}C,\qquad C\xrightarrow{-10}B

由于存在权值为 $-10$ 的边，Dijkstra 的贪心策略可能失效。因此，考试中看到“Dijkstra 可以处理负权边”，通常应判断为错误。

在数据结构考试中，如果题目没有特别说明使用堆优化，通常采用传统实现的 $O(V^2)$ 。

BFS 和 Dijkstra 通常解决的是从一个起点到其他所有顶点的最短路径，而 Floyd 解决的是任意两个顶点之间的最短路径，也称为多源最短路径或全源最短路径。

假设图中有 $A,B,C,D$ 四个顶点，Floyd 一次运行后，不仅能得到 $A$ 到其他顶点的距离，还能得到 $B$ 、 $C$ 、 $D$ 到其他顶点的距离，最终形成完整的距离矩阵。

Floyd 可以处理负权边，但不能存在负权回路。若回路 $A\rightarrow B\rightarrow C\rightarrow A$ 的总权值为 $-5$ ，反复经过该回路会使路径长度变为 $-5,-10,-15,\ldots$ ，因此不存在正常意义上的最短路径。

Floyd 的核心是三重循环，不断更新：

d[i][j]=\min\bigl(d[i][j],\ d[i][k]+d[k][j]\bigr)

三个循环都最多执行 $V$ 次，因此：

V\times V\times V=\boxed{O(V^3)}

其中，“单源”指从一个指定顶点出发，“全源”指求任意两个顶点之间的最短路径。

记忆： BFS——无权单源；Dijkstra——非负权单源；Floyd——全源最短路，可有负权边但不能有负权回路。