本文用到的包

import networkx as nx

考慮如下網(wǎng)絡

流網(wǎng)絡示意圖

這個網(wǎng)絡的構(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)