迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法是图论中最经典的两种最短路径算法，各有其适用场景与实现特点。
1. 迪杰斯特拉算法（Dijkstra）——单源最短路径
- 适用条件：图中边权非负（不能有负权边），适合稀疏图。
- 核心思想：
- 维护一个距离数组
dist[]，表示从源点到各顶点的当前最短距离。 - 使用集合 S 记录已确定最短路径的顶点，T 表示未确定的顶点。
- 每次选择 T 中
dist最小的顶点 u，将其加入 S，并以 u 为中间点松弛其邻接点的距离（即尝试通过 u 改善其他点的距离）。
- 维护一个距离数组
- 时间复杂度：
- 使用邻接矩阵：O(V²)
- 使用优先队列（堆优化）：O((V + E) log V)，适合稀疏图
- 不能处理负权边，因为一旦某个点被标记为“已确定”，就不会再更新，而负权边可能导致后续更短路径出现。
2. 弗洛伊德算法（Floyd）——所有顶点对之间的最短路径
- 适用条件：允许负权边，但不能有负权环；适合稠密图。
- 核心思想：
- 基于动态规划，使用三维状态思想但在二维数组上迭代。
- 初始时用邻接矩阵
dis[i][j]存储直接边权或 ∞。 - 枚举中间点 k（从 1 到 n），更新所有点对 (i, j) 的距离：
ifdis[i][k]+dis[k][j]<dis[i][j]:dis[i][j]=dis[i][k]+dis[k][j] - 经过 n 轮后，
dis[i][j]即为 i 到 j 的最短路径。
- 时间复杂度：O(V³)，空间复杂度 O(V²)
- 优点：代码简洁，易于实现，能检测负权环（只需检查对角线是否有负值）
总结对比：
| 特性 | Dijkstra | Floyd |
|---|---|---|
| 解决问题 | 单源最短路径 | 所有顶点对最短路径 |
| 时间复杂度 | O(V²) 或 O((V+E)logV) | O(V³) |
| 空间复杂度 | O(V) 或 O(V²) | O(V²) |
| 是否支持负权边 | ❌ 不支持 | ✅ 支持（无负权环） |
| 适合图类型 | 稀疏图 | 稠密图 |
| 实现难度 | 中等（需维护集合/堆） | 简单（三重循环） |
使用最小堆（优先队列）优化的 Dijkstra 算法可以显著提升性能，尤其适用于稀疏图。Python 中可通过heapq模块实现最小堆。
✅ 算法步骤（堆优化版）：
- 初始化源点距离为 0，其余顶点距离为 ∞。
- 将
(距离, 顶点)入堆。 - 循环取堆中距离最小的顶点
u，若已访问则跳过。 - 遍历
u的所有邻接点v，尝试通过u松弛v的距离。 - 若找到更短路径，则将新距离入堆。
- 直到堆为空。
⚠️ 注意：同一个顶点可能多次入堆（不同路径长度），我们只处理第一次出堆（最小距离）的情况。
✅ Python 实现代码（邻接表 + 堆优化）
importheapqfromcollectionsimportdefaultdictimportmathdefdijkstra_heap(graph,start):""" 使用最小堆优化的Dijkstra算法求单源最短路径 :param graph: 邻接表，格式 {u: [(v, weight), ...]} :param start: 起始顶点 :return: 字典 dist，表示从 start 到各点的最短距离 """# 初始化距离字典dist=defaultdict(lambda:math.inf)dist[start]=0# 最小堆：(距离, 顶点)heap=[(0,start)]visited=set()whileheap:d,u=heapq.heappop(heap)# 如果该节点已处理，跳过（懒删除）ifuinvisited:continuevisited.add(u)# 遍历邻居forv,wingraph[u]:ifd+w<dist[v]:dist[v]=d+w heapq.heappush(heap,(dist[v],v))returndict(dist)# 示例使用if__name__=="__main__":# 构建图：A=0, B=1, C=2, D=3graph=defaultdict(list)graph[0].append((1,4))graph[0].append((2,1))graph[1].append((3,1))graph[2].append((1,2))graph[2].append((3,5))graph[1].append((2,1))# 双向边示例distances=dijkstra_heap(graph,0)print("最短距离:",distances)# 输出: {0: 0, 2: 1, 1: 3, 3: 4}🔍 输出说明：
- 从节点
0出发：- 到
0: 0 - 到
2: 1 - 到
1: 3（0→2→1） - 到
3: 4（0→2→1→3）
- 到
✅ 时间复杂度分析：
- 时间复杂度：O((V + E) log V)，每条边最多入堆一次，每次堆操作 O(log V)
- 空间复杂度：O(V + E)，存储图与堆
