import matplotlib.pyplot as plt
import networkx as nx
gAnt=nx.Graph()
gAnt.add_weighted_edges_from([(0,1,3),(0,2,1),(0,3,1),
(1,2,1),(1,4,1),(1,9,4),
(2,3,1),(2,4,2),(2,5,1),
(3,5,2),(3,6,2),(3,7,1),
(4,5,1),(4,9,1),
(5,6,1),(5,9,3),(5,10,1),(5,12,3),
(6,7,1),(6,8,2),(6,12,2),(6,13,4),(6,14,3),
(7,8,1),
(8,14,1),(8,15,3),
(9,10,1),(9,11,1),
(10,11,1),(10,12,2),
(11,12,1),(11,16,1),
(12,13,2),(12,16,1),
(13,14,1),(13,15,2),(13,16,2),(13,17,1),
(14,15,1),
(15,17,4),
(16,17,1)])#向图中添加多条赋权边:(node1,node2,weight)
pos={0:(0,8),1:(7,12),2:(6,9),3:(5,6),4:(11,10),5:(14,8),#指定顶点位置
6:(17,6),7:(10,4),8:(19,4),9:(18,12),10:(21,10),11:(28,12),
12:(25,8),13:(30,7),14:(24,5),15:(29,4),16:(32,10),17:(37,8)}
gAnt.remove_nodes_from([5])#通过顶点标签5删除顶点
gAnt.remove_edge(13,17)#删除边(13,17)
minWPath1=nx.dijkstra_path(gAnt,source=0,target=17)#顶点0到顶点17的最短加权路径
lMinWPath1=nx.dijkstra_path_length(gAnt,source=0,target=17)#最短加权路径长度
print("n问题: 禁止边的约束")
print("S 到 E 的最短加权路径: ",minWPath1)
print("S 到 E 的最短加权路径长度: ",lMinWPath1)
edgeList=[]
for i in range(len(minWPath1)-1):
edgeList.append((minWPath1[i],minWPath1[i 1]))
nx.draw_networkx_edges(gAnt,pos,edgelist=edgeList,edge_color='#ffc0cb',width=6)#设置边的颜色
nx.draw(gAnt,pos,with_labels=True,alpha=0.8)
labels=nx.get_edge_attributes(gAnt,'weight')
nx.draw_networkx_edge_labels(gAnt,pos,edge_labels=labels,font_color='c')#显示权值
nx.draw_networkx_nodes(gAnt,pos,nodelist=[0,17],node_color='yellow')#设置顶点颜色
nx.draw_networkx_nodes(gAnt,pos,nodelist=[7,12],node_color='lime')#设置顶点颜色
nx.draw_networkx_edges(gAnt,pos,edgelist=[(2,4),(13,14)],edge_color='lime',width=2.5)#设置边的颜色
nx.draw_networkx_edges(gAnt,pos,edgelist=[(11,12)],edge_color='r',width=2.5)#设置边的颜色
plt.show()问题: 禁止点或禁止边的约束 S 到 E 的最短加权路径: [0, 3, 6, 12, 16, 17] S 到 E 的最短加权路径长度: 7
算法：禁止点或禁止边的最短路径是从图中删除对应的禁止点或禁止边求最短加权路径和最短加权路径长度。
文献：舒兴明. (2002). 拆边法求最短路径. 工科数学.
