Python networkx模块求dijkstra最短路径_networkx dijkstra

a)networkx简介：主要用于创造、操作复杂网络，以及学习复杂网络的结构、动力学及其功能。用于分析网络结构，建立网络模型，设计新的网络算法，绘制网络等等。安装networkx看以参见官网
networkx 基本操作请参考
networkx
python图论包networks(最短路,最小生成树带包)

例题如下

如图求下列各节点间最短距离

代码实现

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
#定义节点数
nodes=np.array(["v1","v2","v3","v4","v5"])
#定义节点间的距离
row=np.array(["v1","v1","v1","v2","v2","v2","v3","v3","v3","v3","v4","v4","v4","v5","v5","v5"])
col=np.array(["v2","v3","v4","v1","v3","v5","v1","v2","v4","v5","v1","v3","v5","v3","v4","v2"])
value=np.array([2,1,4,2,6,3,1,6,3,8,4,3,7,8,7,3])
#生成无向图
G=nx.Graph()
#给图添加节点
for i in range(0,np.size(nodes)):
    G.add_node(nodes[i])
#添加带权的边
for i in range(0,np.size(row)):
    G.add_weighted_edges_from([(row[i],col[i],value[i])])
#设置网路布局
pos=nx.shell_layout(G)
#画出网络图像
nx.draw(G,pos,with_labels=True, node_color='white', edge_color='b', node_size=800, alpha=0.5)
# plt.ion()  # 打开交互模式
# plt.title("slfe_Net")
# plt.ioff()
# plt.show()
edge_labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels)
plt.draw()
plt.pause(1)# 间隔的秒数：3s
plt.close()


'''
Shortest Path with dijkstra_path
'''
#dijkstra方法寻找最短路径
start,end=input("请输入起止节点用空格分开：").split()
path=nx.dijkstra_path(G, source=start, target=end)
print('节点{0}到{1}的路径：'.format(start,end), path)
distance=nx.dijkstra_path_length(G, source=start, target=end)
print('节点{0}到{1}的距离为：'.format(start,end), distance)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

程序说明：此代码运用到matplotlib画图和numpy创建矩阵
运行结果


OK 谢谢关注。