本文用到的包
import networkx as nx
考虑如下网络
流网络示意图
这个网络的构建代码是
G=nx.DiGraph()
G.add_edge(0,1,weight=80)
G.add_edge(1,2,weight=50)
G.add_edge(1,3,weight=30)
G.add_edge(3,2,weight=10)
G.add_edge(2,4,weight=20)
G.add_edge(2,5,weight=30)
G.add_edge(4,5,weight=10)
G.add_edge(5,3,weight=5)
G.add_edge(2,6,weight=10)
G.add_edge(4,6,weight=10)
G.add_edge(3,6,weight=25)
G.add_edge(5,6,weight=35)
可视化绘制使用了Processing，制图代码在这里。
定义如下函数
def Dijkstra(G,start,end):
RG = G.reverse(); dist = {}; previous = {}
for v in RG.nodes():
dist[v] = float('inf')
previous[v] = 'none'
dist[end] = 0
u = end
while u!=start:
u = min(dist, key=dist.get)
distu = dist[u]
del dist[u]
for u,v in RG.edges(u):
if v in dist:
alt = distu + RG[u][v]['weight']
if alt < dist[v]:
dist[v] = alt
previous[v] = u
path=(start,)
last= start
while last != end:
nxt = previous[last]
path += (nxt,)
last = nxt
return path
使用这个函数寻找0与6之间的最小权重路径
Dijkstra(G,0,6)
其结果是
(0, 1, 3, 2, 6)