用NetworkX求解最短路径

文章目录

• • 最短路径
  • 测试代码
  • 小结

最短路径

计算最短路径是经典的图论问题，networkx中提供了最u但路径计算函数【shortest_path】，其函数签名为

shortest_path(G, source=None, target=None, weight=None, method='dijkstra')

其含义是，在G图中，从source到target之间，根据权重weight，采用method算法，计算出最短路径。当weight是字符串时，采用G图中对应的属性作为距离。

method目前支持两种算法，分别是dijkstra和bellman-ford。其中Dijkstra是一种贪心算法，每次都从未确定的节点中挑一个距离源点最近的，然后更新其邻居；Bellman-Ford算法则是基于动态规划与松弛操作。二者主要差异如下

测试代码

下面采用dijkstra算法进行最短路径的测试，测试结果如下

测试代码如下，参考了官方教程，但在绘图时采用了kamada_kawai_layout的布局方式，使得权重越小、边越短，从而更加复合人眼直觉。

import networkx as nx
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = 'Times New Roman'

edges = [("A", "B", 4), ("A", "H", 8), ("B", "C", 8),
("B", "H", 11), ("C", "D", 7), ("C", "F", 4),
("C", "I", 2), ("D", "E", 9), ("D", "F", 14),
("E", "F", 10), ("F", "G", 2), ("G", "H", 1),
("G", "I", 6), ("H", "I", 7)]

G = nx.Graph()
G.add_weighted_edges_from(edges)

# 寻找A到F的最短路径
path = nx.shortest_path(G, "A", "E", weight="weight")

# 创建最短路径的边列表
path_edges = list(zip(path, path[1:]))

edge_colors = [
"red" if edge in path_edges or tuple(reversed(edge)) in path_edges else "black"
for edge in G.edges()
]

pos = nx.kamada_kawai_layout(G, weight="weight")

nx.draw_networkx_nodes(G, pos)
nx.draw_networkx_edges(G, pos, edge_color=edge_colors)
nx.draw_networkx_labels(G, pos)
nx.draw_networkx_edge_labels(
G, pos, edge_labels={(u, v): d["weight"] for u, v, d in G.edges(data=True)}
)

plt.show()

小结

本文介绍了networkx库中的最短路径计算函数shortest_path，支持Dijkstra和Bellman-Ford两种算法，并对比了它们在负权边处理、负权环检测和时间复杂度上的差异。通过测试代码演示了Dijkstra算法的应用，采用kamada_kawai_layout布局使权重可视化更直观。结果显示，从节点A到E的最短路径为红色高亮边。该函数适用于加权图中的最短路径查找，可根据需求选择不同算法。