文章目录最短路径测试代码小结最短路径计算最短路径是经典的图论问题networkx中提供了最u但路径计算函数【shortest_path】其函数签名为shortest_path(G,sourceNone,targetNone,weightNone,methoddijkstra)其含义是在G图中从source到target之间根据权重weight采用method算法计算出最短路径。当weight是字符串时采用G图中对应的属性作为距离。method目前支持两种算法分别是dijkstra和bellman-ford。其中Dijkstra是一种贪心算法每次都从未确定的节点中挑一个距离源点最近的然后更新其邻居Bellman-Ford算法则是基于动态规划与松弛操作。二者主要差异如下dijkstrabellman-ford负权边处理❌✅负权环检测❌✅时间复杂度O ( ( V E ) log ⁡ V ) O((VE)\log V)O((VE)logV)O ( V E ) O(VE)O(VE)测试代码下面采用dijkstra算法进行最短路径的测试测试结果如下测试代码如下参考了官方教程但在绘图时采用了kamada_kawai_layout的布局方式使得权重越小、边越短从而更加复合人眼直觉。importnetworkxasnximportmatplotlib.pyplotasplt plt.rcParams[font.sans-serif]Times New Romanedges[(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)]Gnx.Graph()G.add_weighted_edges_from(edges)# 寻找A到F的最短路径pathnx.shortest_path(G,A,E,weightweight)# 创建最短路径的边列表path_edgeslist(zip(path,path[1:]))edge_colors[redifedgeinpath_edgesortuple(reversed(edge))inpath_edgeselseblackforedgeinG.edges()]posnx.kamada_kawai_layout(G,weightweight)nx.draw_networkx_nodes(G,pos)nx.draw_networkx_edges(G,pos,edge_coloredge_colors)nx.draw_networkx_labels(G,pos)nx.draw_networkx_edge_labels(G,pos,edge_labels{(u,v):d[weight]foru,v,dinG.edges(dataTrue)})plt.show()小结本文介绍了networkx库中的最短路径计算函数shortest_path支持Dijkstra和Bellman-Ford两种算法并对比了它们在负权边处理、负权环检测和时间复杂度上的差异。通过测试代码演示了Dijkstra算法的应用采用kamada_kawai_layout布局使权重可视化更直观。结果显示从节点A到E的最短路径为红色高亮边。该函数适用于加权图中的最短路径查找可根据需求选择不同算法。