本文用到的包
import networkx as nx
考慮如下網(wǎng)絡(luò)
流網(wǎng)絡(luò)示意圖
這個網(wǎng)絡(luò)的構(gòu)建代碼是
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潭苞，制圖代碼在這里拂玻。
定義如下函數(shù)
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
使用這個函數(shù)尋找0與6之間的最小權(quán)重路徑
Dijkstra(G,0,6)
其結(jié)果是
(0, 1, 3, 2, 6)