額外的限制期間使用NetworkX

Question

加權圖搜索最短路徑我有問題你如何使用NetworkX

加權圖搜索最短路徑過程中添加額外的約束

示例圖：

G.add_edge(A, B, weight=1) 
G.add_edge(B, C, weight=2) 
G.add_edge(A, C, weight=1) 
.. 
.. 
.. 
G.add_edge(Y, Z, weight=6) 

所以，現在我想找到從A到F的最短路徑，包括一些點，例如：C，L，G，R（排序沒有意義）。如何使用NetworkX。

謝謝！

Answer 1

這可能不是最好的解決辦法，但無論如何：

import networkx as nx 
from string import letters 
from random import sample, randint 
from itertools import permutations 

# generate random graph  
G = nx.Graph() 

nodes = list(letters[:20]) 

for anode in nodes: 
    G.add_node(anode, weight=randint(1,20)) 

for edge in [sample(nodes, 2) for i in range(60)]: 
    G.add_edge(*edge) 

現在，讓我們來定義路徑搜索功能：

def multiple_dijkstra(G, apath, result, n=0, i=1): 
    """For a path of: a - b - c - d, search recursively for the shortest 
    paths between 'a' and 'b', then 'b' and 'c', then 'c' and 'd'. 
    Return a list which is a path from 'a' to 'd' through 'b' and 'c'.""" 
    try: 
     result.extend(nx.dijkstra_path(G, apath[n], apath[i])[:-1]) 
     multiple_dijkstra(G, apath, result, n+1, i+1) 
     return result 
    except IndexError: 
     result.extend(nx.dijkstra_path(G, apath[n], apath[i-1])) 
     return result 

def possible_paths(start_node, end_node, *between): 
    """Generate all possible paths based on permutations of *between""" 
    for permutation in permutations(between, len(between)): 
     yield [start_node] + list(permutation) + [end_node] 

def gothrough_possible_paths(start_node, end_node, *between): 
    """Test all permutations for shortest path""" 
    for apath in possible_paths(start_node, end_node, *between): 
     result = [] 
     shortest_path = multiple_dijkstra(G, apath, result) 
     print 'Testing path: {}\nResult: {} (length: {})'.format(
          ' - '.join(apath), 
          ' - '.join(shortest_path), 
          len(shortest_path)) 

現在，我們可以尋找最短路徑：

# let's pick 5 random nodes: a start node, end node and three in-between nodes 
n1, n2, n3, n4, n5 = sample(nodes, 5) 

# ...and search for the shortest paths between 'n1' and 'n2' 
# such that 'n3', 'n4' and 'n5' are in-between nodes 
gothrough_possible_paths(n1, n2, n3, n4, n5) 

可能出現的結果：

Testing path: e - h - g - j - t 
Result: e - k - h - k - g - k - b - j - b - t (length: 10) 
Testing path: e - h - j - g - t 
Result: e - k - h - k - b - j - o - c - g - k - b - t (length: 12) 
Testing path: e - g - h - j - t 
Result: e - k - g - k - h - k - b - j - b - t (length: 10) 
Testing path: e - g - j - h - t 
Result: e - k - g - k - b - j - b - k - h - l - t (length: 11) 
Testing path: e - j - h - g - t 
Result: e - j - b - k - h - k - g - k - b - t (length: 10) 
Testing path: e - j - g - h - t 
Result: e - j - o - c - g - k - h - l - t (length: 9) 

所以，從e到t的最短路徑是通過j，g和h（按照這個順序），以及實際軌跡是：e - j - o - c - g - k - h - l - t。

我不是這方面的專家，所以我很好奇的更好的解決方案。但希望這有助於。