最短路算法流程

1. Floyd（$O(n^3)$，多源最短路径）

1. 初始化一个 $n \times n$ 的距离矩阵 $\text{dist}$，其中 $\text{dist}_{i,j}$ 表示顶点 $i$ 到顶点 $j$ 的初始距离：
   • 若 $i = j$，则 $\text{dist}_{i,j} = 0$；
   • 若顶点 $i$ 和 $j$ 之间有直接边，$\text{dist}_{i,j}$ 设为边的权重；
   • 否则，$\text{dist}_{i,j} = \infty$（无穷大）。
2. 遍历所有中间顶点 $k$（从 $1$ 到 $n$）：
   • 遍历所有起点 $i$（从 $1$ 到 $n$）：
     • 遍历所有终点 $j$（从 $1$ 到 $n$）：
       • 如果 $\text{dist}_{i,j} > \text{dist}_{i,k} + \text{dist}_{k,j}$，则更新 $\text{dist}_{i,j} = \text{dist}_{i,k} + \text{dist}_{k,j}$。
3. 算法结束后，$\text{dist}_{i,j}$ 即为顶点 $i$ 到顶点 $j$ 的最短路径距离。

2. 朴素 Dijkstra（$O(n^2)$，无负权边）

1. 给定起点 $s$，初始化距离数组 $\text{dist}$：$\text{dist}_s = 0$，其他顶点 $\text{dist}_i = \infty$；初始化一个标记数组 $\text{visited}$，所有元素为 $\text{false}$（表示未访问）。
2. 执行 $n$ 次循环（$n$ 为顶点数）：
   • 在未访问的顶点中，找到距离起点最近的顶点 $u$（即 $\text{dist}_u$ 最小且 $\text{visited}_u = \text{false}$）。
   • 标记 $u$ 为已访问（$\text{visited}_u = \text{true}$）。
   • 遍历 $u$ 的所有邻接顶点 $v$：
     • 如果 $\text{dist}_v > \text{dist}_u + \text{边}(u, v)\text{的权重}$，则更新 $\text{dist}_v = \text{dist}_u + \text{边}(u, v)\text{的权重}$。
3. 算法结束后，$\text{dist}_i$ 即为起点 $s$ 到顶点 $i$ 的最短路径距离。

3. 堆优化 Dijkstra（$O(m\log n)$，无负权边）

1. 给定起点 $s$，初始化距离数组 $\text{dist}$：$\text{dist}_s = 0$，其他顶点 $\text{dist}_i = \infty$；使用一个优先队列（小根堆），存储 $(\text{距离}, \text{顶点})$ 对，初始将 $(0, s)$ 入堆。
2. 当 优先队列不为空 时：
   • 弹出堆顶元素 $(\text{current\_dist}, u)$（即当前距离起点最近的顶点 $u$）。
   • 如果 $\text{current\_dist} > \text{dist}_u$，则跳过该顶点（已处理过更优路径）。
   • 遍历 $u$ 的所有邻接顶点 $v$：
     • 计算新距离 $\text{new\_dist} = \text{dist}_u + \text{边}(u, v)\text{的权重}$。
     • 如果 $\text{new\_dist} < \text{dist}_v$：
       • 更新 $\text{dist}_v = \text{new\_dist}$。
       • 将 $(\text{new\_dist}, v)$ 入堆。
3. 算法结束后，$\text{dist}_i$ 即为起点 $s$ 到顶点 $i$ 的最短路径距离。

4. Bellman-Ford（$O(nm)$，能处理负权边）

1. 给定起点 $s$，初始化距离数组 $\text{dist}$：$\text{dist}_s = 0$，其他顶点 $\text{dist}_i = \infty$。
2. 执行 $n-1$ 次循环（$n$ 为顶点数）：
   • 遍历所有边 $(u, v)$：
     • 如果 $\text{dist}_u \neq \infty$ 且 $\text{dist}_v > \text{dist}_u + \text{边}(u, v)\text{的权重}$，则更新 $\text{dist}_v = \text{dist}_u + \text{边}(u, v)\text{的权重}$。
3. 检测负权环：
   • 再次遍历所有边 $(u, v)$：
     • 如果 $\text{dist}_u \neq \infty$ 且 $\text{dist}_v > \text{dist}_u + \text{边}(u, v)\text{的权重}$，则说明图中存在负权环，无法计算最短路径。
4. 若不存在负权环，$\text{dist}_i$ 即为起点 $s$ 到顶点 $i$ 的最短路径距离。

5. SPFA（$O(km)\sim O(nm)$，能处理负权边）

1. 给定起点 $s$，初始化距离数组 $\text{dist}$：$\text{dist}_s = 0$，其他顶点 $\text{dist}_i = \infty$；使用一个队列存储待松弛的顶点，初始将 $s$ 入队；初始化一个入队次数数组 $\text{cnt}$，$\text{cnt}_s = 1$，其他为 0。
2. 当 队列不为空 时：
   • 出队顶点 $u$。
   • 遍历 $u$ 的所有邻接顶点 $v$：
     • 计算新距离 $\text{new\_dist} = \text{dist}_u + \text{边}(u, v)\text{的权重}$。
     • 如果 $\text{new\_dist} < \text{dist}_v$：
       • 更新 $\text{dist}_v = \text{new\_dist}$。
       • 如果 $v$ 不在队列中：
         • 将 $v$ 入队。
         • $\text{cnt}_v += 1$。
         • 如果 $\text{cnt}_v \geq n$（$n$ 为顶点数），则说明存在负权环，算法终止。
3. 若未检测到负权环，$\text{dist}_i$ 即为起点 $s$ 到顶点 $i$ 的最短路径距离。