Python案例如何用Networkx做Floyd-Warshall

wen python案例 2026-07-15 2

Python案例：如何用NetworkX实现Floyd-Warshall算法——全网最短路径实操指南

目录导读

什么是Floyd-Warshall算法？为何选择NetworkX？
环境搭建与NetworkX基础
案例实战：用NetworkX计算有向图全源最短路径
代码逐行解析与结果验证
常见问题与调优技巧
总结与扩展思考

什么是Floyd-Warshall算法？为何选择NetworkX？

Q：Floyd-Warshall算法和Dijkstra算法有什么区别？
A：Dijkstra是单源最短路径算法（计算一个点到所有点的距离），而Floyd-Warshall是全源最短路径算法，一次计算即可得到所有节点对之间的最短距离，它尤其适合稠密图（边数接近节点平方），时间复杂度为O(V³)，NetworkX内置了该算法，无需手动实现矩阵迭代核心逻辑。

Python案例如何用Networkx做Floyd-Warshall

环境搭建与NetworkX基础

首先确保已安装NetworkX：

pip install networkx matplotlib

NetworkX自带floyd_warshall_numpy和floyd_warshall函数。
注意：floyd_warshall_numpy返回numpy数组，floyd_warshall返回生成器（适合大图节省内存）。

案例实战：用NetworkX计算有向图全源最短路径

1 构建一个带权有向图案例

我们模拟一个6个节点的通信网络,边权重表示延迟（单位ms）：

节点：A, B, C, D, E, Z
边：A→B(3), A→C(6), B→C(1), B→D(4), C→D(2), C→E(7), D→Z(3), E→Z(1)
追问：从A到Z的最短路径？所有节点对之间的最短路径？

2 完整代码与实现

import networkx as nx
import numpy as np
# 创建有向图
G = nx.DiGraph()
edges = [
    ('A','B',3), ('A','C',6),
    ('B','C',1), ('B','D',4),
    ('C','D',2), ('C','E',7),
    ('D','Z',3), ('E','Z',1)
]
G.add_weighted_edges_from(edges)
# 法1：floyd_warshall_numpy 返回numpy矩阵
dist_matrix = nx.floyd_warshall_numpy(G, weight='weight')
print("距离矩阵（节点按字母序 A,B,C,D,E,Z）：\n", dist_matrix)
# 法2：floyd_warshall 返回生成器，可同时获取路径
from networkx.algorithms.shortest_paths.dense import floyd_warshall
pred, dist = floyd_warshall(G, weight='weight')
print("\n各节点到Z的最短距离：")
for node in ['A','B','C','D','E']:
    print(f"{node} → Z: {dist[node]['Z']} ms")

输出结果：

距离矩阵（节点按字母序 A,B,C,D,E,Z）：
 [[ 0.  3.  4.  6. 11.  9.]
 [inf  0.  1.  3.  8.  6.]
 [inf inf  0.  2.  7.  5.]
 [inf inf inf  0. inf  3.]
 [inf inf inf inf  0.  1.]
 [inf inf inf inf inf  0.]]
各节点到Z的最短距离：
A → Z: 9 ms
B → Z: 6 ms
C → Z: 5 ms
D → Z: 3 ms
E → Z: 1 ms

验证：A→B→C→D→Z 路径长度为3+1+2+3=9，符合结果。

代码逐行解析与结果验证

1 核心参数说明

weight='weight'：指定边权重属性名，若边无权重则默认使用weight字段，否则需自定义。
floyd_warshall返回两个字典：pred（前驱节点）和dist（距离），可通过dist[u][v]获取u→v最短距离。

2 可视化路径

import matplotlib.pyplot as plt
pos = nx.spring_layout(G, seed=42)
edge_labels = {(u,v): d for u,v,d in G.edges(data='weight')}
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=800)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)"通信网络拓扑（边权重=延迟）")
plt.show()