数学建模--图论最短路径，Python的Networkx包实现_networkx的floyd

import networkx as nx
import matplotlib.pyplot as plt
1
2

第一种方式画图

# 节点名称
nodes = [0,1,2,3,4,5,6,7,8]
# 边列表，格式为：（节点，节点，权重）
edgess = [(0,1,3), (0,7,8), (1,7,3), (1,2,8), (7,8,1), (7,6,6), (8,2,2),
         (8,6,6), (2,5,4), (6,5,2), (2,3,7), (3,5,14), (3,4,9), (5,4,10)]
# 创建Graph对象
G = nx.Graph()
# 添加节点
G.add_nodes_from(nodes)
# 添加带权重的边
G.add_weighted_edges_from(edgess)
# 绘图并设置各种参数
nx.draw_networkx(G, node_color='b', font_color='w', font_weight='bold')
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14

0-4间的最短路径及距离（无向图）

# method参数默认为'dijkstra'，当边有向时，可以选择'bellman-ford'
p = nx.shortest_path(G, source=0, weight='weight', method='dijkstra')
print('0到4的最短路径为:',p[4])
d = nx.shortest_path_length(G, source=0, target=4, weight='weight')
print('0到4的最短距离为:',d)
1
2
3
4
5

0到4的最短路径为: [0, 1, 7, 8, 2, 5, 4]
0到4的最短距离为: 23
1
2

方法二

# 第二个参数为'4'时，返回各个节点到'4'的最短路径
path=nx.single_source_dijkstra_path(G,4)

# 第二个参数为'4'时，返回各个节点到'4'的最短路径的距离
length=nx.single_source_dijkstra_path_length(G,4)


print(path)
print('----------------------------------------------------')
print(length)
1
2
3
4
5
6
7
8
9
10

{4: [4], 3: [4, 3], 5: [4, 5], 2: [4, 5, 2], 6: [4, 5, 6], 7: [4, 5, 2, 8, 7], 8: [4, 5, 2, 8], 1: [4, 5, 2, 8, 7, 1], 0: [4, 5, 2, 8, 7, 1, 0]}
----------------------------------------------------
{4: 0, 3: 9, 5: 10, 6: 12, 2: 14, 8: 16, 7: 17, 1: 20, 0: 23}
1
2
3

高亮最短路径

Y = nx.Graph()

# 添加带权边，edgess同上
for i in edgess:
    Y.add_edge(i[0], i[1], weight=i[2])
1
2
3
4
5

edgelists = []

# p[4]为0-4最短路径所经过的节点
point = p[4]
for i in range(len(point) - 1):
    edgelists.append((point[i], point[i+1]))
# print(edgelists)

# 设置节点    
pos=nx.spring_layout(Y)
nx.draw_networkx_nodes(Y,pos,node_size=700)

# 绘画所有边
nx.draw_networkx_edges(Y, pos)
# 绘画需要高亮的边
nx.draw_networkx_edges(Y, pos, edgelist=edgelists, edge_color='y', width=3)
# 显示并设置标号
nx.draw_networkx_labels(Y,pos,font_size=15,font_family='sans-serif', font_color='w')

# 不显示坐标轴
plt.axis('off')
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Floyd-Warshall算法

# 该函数返回所有节点与各个节点之间的最短路径，及距离
predecessors, _ = nx.floyd_warshall_predecessor_and_distance(G)
pred = nx.reconstruct_path(0,4,predecessors)
print('0到4的最短路径为：', pred)
1
2
3
4

0到4的最短路径为： [0, 1, 7, 8, 2, 5, 4]
1

# 该函数返回一个任意两点间最短距离的矩阵
distance = nx.floyd_warshall_numpy(G)
dist = distance[4,0]
print('0到4的最短距离为：', dist)
1
2
3
4

0到4的最短距离为： 23.0
1