迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法是图论中最经典的两种最短路径算法

迪杰斯特拉（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 算法可以显著提升性能，尤其适用于稀疏图。Python 中可通过heapq模块实现最小堆。

✅ 算法步骤（堆优化版）：

1. 初始化源点距离为 0，其余顶点距离为 ∞。
2. 将(距离, 顶点)入堆。
3. 循环取堆中距离最小的顶点u，若已访问则跳过。
4. 遍历u的所有邻接点v，尝试通过u松弛v的距离。
5. 若找到更短路径，则将新距离入堆。
6. 直到堆为空。

⚠️ 注意：同一个顶点可能多次入堆（不同路径长度），我们只处理第一次出堆（最小距离）的情况。

✅ 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)，存储图与堆