企业官网建设流程全解析

图论算法实战：Dijkstra 与 Floyd 求解 6 节点最短路径代码对比

在计算机科学中，图论算法是解决网络结构问题的核心工具。无论是社交网络分析、路径规划还是系统依赖管理，最短路径问题都是最基础且实用的场景之一。本文将深入探讨两种经典的最短路径算法——Dijkstra 算法和 Floyd-Warshall 算法，并通过一个 6 节点有向网的完整 Python 实现，直观对比它们的实现逻辑、适用场景和性能差异。

1. 算法原理与核心思想

1.1 Dijkstra 算法：单源最短路径的贪心策略

Dijkstra 算法由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出，其核心是通过逐步扩展已知最短路径集合来找到从单一源点到所有其他顶点的最短路径。该算法采用贪心策略，每次选择当前距离源点最近的未处理顶点进行松弛操作。

算法步骤：

1. 初始化：设置源点到自身的距离为 0，其他顶点到源点的距离为无穷大
2. 选择当前未处理顶点中距离源点最近的顶点 u
3. 对 u 的所有邻居顶点 v 进行松弛操作：
   • 如果通过 u 到 v 的路径比已知路径更短，则更新 v 的距离
4. 将 u 标记为已处理
5. 重复步骤 2-4 直到所有顶点都被处理

import heapq def dijkstra(graph, start): distances = {vertex: float('infinity') for vertex in graph} distances[start] = 0 priority_queue = [(0, start)] while priority_queue: current_distance, current_vertex = heapq.heappop(priority_queue) if current_distance > distances[current_vertex]: continue for neighbor, weight in graph[current_vertex].items(): distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) return distances

1.2 Floyd-Warshall 算法：多源最短路径的动态规划方案

Floyd-Warshall 算法采用动态规划思想，通过逐步考虑所有可能的中间顶点来更新最短路径估计。与 Dijkstra 不同，它能处理图中存在负权边（但不能有负权环）的情况，并一次性计算出所有顶点对之间的最短路径。

算法步骤：

1. 初始化距离矩阵，对角线为 0，直接相连的边为权重，其他为无穷大
2. 对于每个中间顶点 k：
   • 对于每对顶点 i 和 j：
     • 如果通过 k 的路径比已知路径更短，则更新距离
3. 最终得到的距离矩阵即为所有顶点对的最短路径

def floyd_warshall(graph): vertices = list(graph.keys()) n = len(vertices) dist = [[float('inf')] * n for _ in range(n)] # 初始化距离矩阵 for i in range(n): dist[i][i] = 0 for neighbor, weight in graph[vertices[i]].items(): j = vertices.index(neighbor) dist[i][j] = weight # 动态规划核心 for k in range(n): for i in range(n): for j in range(n): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] return {vertices[i]: {vertices[j]: dist[i][j] for j in range(n)} for i in range(n)}

2. 6 节点有向网的实现与对比

2.1 构建测试图结构

我们设计一个 6 节点的有向带权图，节点标记为 A 到 F：

graph = { 'A': {'B': 4, 'C': 2}, 'B': {'C': 5, 'D': 10}, 'C': {'E': 3}, 'D': {'F': 11}, 'E': {'D': 4}, 'F': {} }

图结构可视化：

A --4--> B --10--> D --11--> F \ / ^ \2 /5 / C --3--> E --4

2.2 Dijkstra 算法执行过程分析

以源点 A 为例，Dijkstra 算法的执行步骤如下：

1. 初始化距离：{'A': 0, 'B': ∞, 'C': ∞, 'D': ∞, 'E': ∞, 'F': ∞}
2. 处理 A：
   • 更新 B: min(∞, 0+4) = 4
   • 更新 C: min(∞, 0+2) = 2
3. 选择最小未处理顶点 C：
   • 更新 E: min(∞, 2+3) = 5
4. 选择最小未处理顶点 B：
   • 更新 D: min(∞, 4+10) = 14
5. 选择最小未处理顶点 E：
   • 更新 D: min(14, 5+4) = 9
6. 选择最小未处理顶点 D：
   • 更新 F: min(∞, 9+11) = 20
7. 最后处理 F（无操作）

最终结果：

{'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}

2.3 Floyd-Warshall 算法执行过程

Floyd 算法的距离矩阵初始状态：

经过 k=0(A)到 k=5(F)的迭代后，最终距离矩阵：

2.4 关键对比指标

3. 算法优化与工程实践

3.1 Dijkstra 的优先队列优化

使用二叉堆实现的优先队列可以显著提升 Dijkstra 算法的性能：

def dijkstra_optimized(graph, start): distances = {vertex: float('infinity') for vertex in graph} distances[start] = 0 heap = [(0, start)] visited = set() while heap: current_distance, current_vertex = heapq.heappop(heap) if current_vertex in visited: continue visited.add(current_vertex) for neighbor, weight in graph[current_vertex].items(): distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(heap, (distance, neighbor)) return distances

3.2 Floyd 算法的路径重建

除了计算最短距离，我们还可以记录路径信息：

def floyd_warshall_with_path(graph): vertices = list(graph.keys()) n = len(vertices) dist = [[float('inf')] * n for _ in range(n)] next_node = [[None] * n for _ in range(n)] # 初始化 for i in range(n): dist[i][i] = 0 for neighbor, weight in graph[vertices[i]].items(): j = vertices.index(neighbor) dist[i][j] = weight next_node[i][j] = j # 动态规划 for k in range(n): for i in range(n): for j in range(n): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] next_node[i][j] = next_node[i][k] return dist, next_node def reconstruct_path(start, end, next_node, vertices): if next_node[start][end] is None: return [] path = [vertices[start]] while start != end: start = next_node[start][end] path.append(vertices[start]) return path

4. 实际应用场景选择指南

4.1 何时选择 Dijkstra 算法

• 单源点查询：当只需要从一个固定起点计算最短路径时
• 稀疏图处理：图中边数远少于顶点数的平方时
• 实时系统：需要快速响应单个查询的场景
• 正权图：图中不存在负权边的情况

提示：在路由协议如 OSPF 中，Dijkstra 被广泛用于计算最短路径树

4.2 何时选择 Floyd-Warshall 算法

• 全源点查询：需要计算所有顶点对之间的最短路径
• 密集图分析：图中边数接近顶点数的平方时
• 预处理场景：可以预先计算并存储结果供后续查询
• 含负权边：图中存在负权边但不含负权环的情况

性能对比实验数据：

从实验数据可以看出，随着节点数量增加，Floyd 算法的立方级时间复杂度使其性能下降明显，而 Dijkstra 算法在稀疏图中表现更为优秀。