用networkx解决图论问题（2）

发表于 更新于
最小生成树应用范例。

例：已知8口油井相互之间的距离如下表所示。其中1号油井离海岸最近，为5nmile（1nmile = 1.852km）。问从海岸经1号油井铺设油管将各油井连接起来，应如何铺设使油管长度最短。

1 2 3 4 5 6 7 8
1 0 1.3 2.1 0.9 0.7 1.8 2.0 1.5
2 0 0.9 1.8 1.2 2.6 2.3 1.1
3 0 2.6 1.7 2.5 1.9 1.0
4 0 0.7 1.6 1.5 0.9
5 0 0.9 1.1 0.8
6 0 0.6 1.0
7 0 0.5
8 0 

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
import numpy as np
import networkx as nx
import pandas as pd
import matplotlib.pyplot as plt

w = [[0,   1.3, 2.1, 0.9, 0.7, 1.8, 2.0, 1.5],
     [1.3,   0, 0.9, 1.8, 1.2, 2.6, 2.3, 1.1],
     [2.1, 0.9,   0, 2.6, 1.7, 2.5, 1.9, 1.0],
     [0.9, 1.8, 2.6,   0, 0.7, 1.6, 1.5, 0.9],
     [0.7, 1.2, 1.7, 0.7,   0, 0.9, 1.1, 0.8],
     [1.8, 2.6, 2.5, 1.6, 0.9,   0, 0.6, 1.0],
     [2.0, 2.3, 1.9, 1.5, 1.1, 0.6,   0, 0.5],
     [1.5, 1.1, 1.0, 0.9, 0.8, 1.0, 0.5,   0]]

G = nx.Graph(np.matrix(w))
T = nx.minimum_spanning_tree(G)

w_t = nx.to_numpy_matrix(T) # 最小生成树的邻接矩阵
print(w_t)
l = w_t.sum()/2+5
print('油管长度l=', l)

s = dict(zip(range(8), range(1,9)))
pos = nx.shell_layout(G)
nx.draw(T, pos, node_size=280, labels=s, node_color='r')
w_t2 = nx.get_edge_attributes(T, 'weight')
nx.draw_networkx_edge_labels(T, pos, edge_labels=w_t2)
plt.show()