定向，加權平衡樹的進口和最短路徑networkx

Question

我有一個平衡的樹分支因子2和高度100，每邊有一個被看起來像一個文本文件中給出的重量：

73 41 
52 40 09 
26 53 06 34 
etc etc until row nr 99 

即：從節點0到1的邊權重爲73，從0到2爲41，從1到3爲52等。

我希望從中找到最短路徑（與相應的邊權重和）根到樹的末尾。據我所知，這可以通過將所有邊權重乘以-1並使用Networkx中的Dijkstra算法來完成。

1. 算法選擇是否正確？
2. 如何「輕鬆」將此數據集導入到Networkx圖形對象中？

（PS：這是項目歐拉Problem 67，發現在數量上的三角形的最大和我已經解決了與記憶化遞歸的問題，但我想嘗試與Networkx包解決它。 ）

Answer 1

是算法的選擇是否正確？

是的。您可以使用正數權重，並撥打nx.dijkstra_predecessor_and_distance以獲得從根節點0開始的最短路徑。

---

我如何「輕鬆地」進口此數據集爲Networkx圖形對象？

import networkx as nx 
import matplotlib.pyplot as plt 

def flatline(iterable): 
    for line in iterable: 
     for val in line.split(): 
      yield float(val) 

with open(filename, 'r') as f: 
    G = nx.balanced_tree(r = 2, h = 100, create_using = nx.DiGraph()) 
    for (a, b), val in zip(G.edges(), flatline(f)): 
     G[a][b]['weight'] = val 

# print(G.edges(data = True)) 

pred, distance = nx.dijkstra_predecessor_and_distance(G, 0) 

# Find leaf whose distance from `0` is smallest 
min_dist, leaf = min((distance[node], node) 
        for node, degree in G.out_degree_iter() 
        if degree == 0) 
nx.draw(G) 
plt.show() 

Answer 2

我不知道我非常理解輸入格式。但是，類似這樣的東西應該工作：

from itertools import count 
import networkx as nx 
adj ="""73 41 
52 40 09 
26 53 06 34""" 
G = nx.Graph() 
target = 0 
for source,line in zip(count(),adj.split('\n')): 
    for weight in line.split(): 
     target += 1 
     print source,target,weight 
     G.add_edge(source,target,weight=float(weight)) 
# now call shortest path with weight="weight" and source=0