Python案例详解：如何用Networkx实现Dijkstra最短路径算法（附完整代码）
目录导读
Dijkstra算法与Networkx简介
1 算法原理
Dijkstra（戴克斯特拉算法）由荷兰计算机科学家Edsger W. Dijkstra于1956年提出，用于求解单源最短路径问题，其核心思想是：从起点出发，每次选择距离最近且未被访问的顶点，并更新其邻居的距离，该算法要求图中所有边的权重为非负数。
2 为什么用Networkx？
Networkx是Python最流行的复杂网络分析库,内置了shortest_path和dijkstra_path等函数，相比手动实现堆优化的Dijkstra，Networkx提供了：
- 一行代码求解（
nx.dijkstra_path） - 自动处理图的结构（有向/无向）
- 支持路径可视化（配合matplotlib）
环境搭建与基础准备
1 安装必要库
pip install networkx matplotlib
2 基础图创建
import networkx as nx
# 创建有向图（带权重）
G = nx.DiGraph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
核心案例：构建加权图并求解最短路径
案例场景
假设有6个城市（A-F），道路权重代表行驶时间（分钟），求从城市A到F的最短时间路线。
import networkx as nx
import matplotlib.pyplot as plt
# 1. 创建有向加权图
G = nx.DiGraph()
edges = [
('A', 'B', 5), ('A', 'C', 3),
('B', 'D', 2), ('C', 'D', 6),
('C', 'E', 4), ('D', 'E', 1),
('D', 'F', 7), ('E', 'F', 2)
]
G.add_weighted_edges_from(edges)
# 2. 计算最短路径（使用Networkx内置函数）
source = 'A'
target = 'F'
path = nx.dijkstra_path(G, source, target, weight='weight')
distance = nx.dijkstra_path_length(G, source, target, weight='weight')
print(f"最短路径: {' -> '.join(path)}")
print(f"总距离: {distance}")
# 输出: 最短路径: A -> C -> E -> F
# 总距离: 9
可视化代码：
pos = nx.spring_layout(G, seed=42) nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=500) edge_labels = nx.get_edge_attributes(G, 'weight') nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) path_edges = list(zip(path, path[1:])) nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2) plt.show()
代码逐段解析（附问答）
Q1：为什么选择nx.dijkstra_path而非nx.shortest_path？
A：nx.shortest_path默认权重为1（即BFS），而Dijkstra专用函数会明确考虑边权重，如果图中权重代表真实距离，必须使用nx.dijkstra_path。
Q2：如何确认图是无环的？
A：Dijkstra允许有环，只要权重非负，但如果有负权边，算法会失效（此时应使用Bellman-Ford）。
Q3：add_weighted_edges_from与手动添加有何区别？
A：该方法自动将前两个参数作为节点，第三个参数作为weight属性，等效于G.add_edge('A','B', weight=5)。
高级扩展：自定义节点名称与权重函数
# 使用复杂权重计算（例如时间=距离/速度）
G.add_edge('X', 'Y', distance=100, speed=50) # 权重2小时
def custom_weight(u, v, d):
return d['distance'] / d['speed']
path = nx.dijkstra_path(G, 'X', 'Z', weight=custom_weight)
进阶：处理负权边与性能优化
1 负权边检测
Networkx默认的Dijkstra不支持负权边，如果图中存在负权，运行时会抛出NetworkXError，此时应改用Bellman-Ford：
# 对于负权图 path = nx.bellman_ford_path(G, 'A', 'F', weight='weight')
2 性能优化技巧
- 使用稀疏图：Networkx的Dijkstra基于堆优化，复杂度O((E+V)log V)
- 批量查询：使用
nx.single_source_dijkstra_path获取从起点到所有节点的最短路径 - 预计算：如果图不变但需多次查询，可建立所有节点对最短路径矩阵
# 批量查询示例
paths = nx.single_source_dijkstra_path(G, 'A', weight='weight')
# 输出: {'A': ['A'], 'B': ['A','B'], ...}
常见问题FAQ
Q4：Networkx的Dijkstra能处理百万节点图吗？
A：可以，但建议使用nx.Graph（无向）而非DiGraph以节省内存，对于超大规模图，可考虑nx.lazy_dijkstra或切换到igraph库。
Q5：如何输出所有最短路径（而非仅一条）？
A：使用nx.all_shortest_paths(G, source, target, weight='weight')，但注意该函数会返回生成器。
all_paths = list(nx.all_shortest_paths(G, 'A', 'F', weight='weight')) # [['A','C','E','F']] 本例仅一条
Q6：边权重为0会导致什么？
A：权重为0的边会被Dijkstra视为“免费路线”，算法依然正确，但如果图中有负权且为0的边，需谨慎。
Q7：如何检查图是否连通？
# 有向图强连通分量检查
if nx.is_strongly_connected(G):
print("图是强连通的")
本文通过一个完整的Python案例,从安装库到可视化，详细演示了如何使用Networkx实现Dijkstra最短路径算法，重点包括：
- 使用
nx.dijkstra_path一行代码求解 - 结合matplotlib绘制路径高亮图
- 处理负权边和性能优化场景
立即行动：将上述代码复制到Jupyter Notebook中运行，尝试修改起点/终点观察路径变化，并在你的项目中应用这一强大的图分析工具。
