4

分岐係数 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: これは Project Euler Problem 67で、三角形の数字の最大和を見つけます。メモ化を使用した再帰で問題を解決しましたが、Networkx パッケージで解決したいと考えています。 )

4

2 に答える 2

4

アルゴリズムの選択は正しいですか?

はい。正の重みを使用し、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()
于 2012-11-24T23:35:35.320 に答える
3

入力形式をよく理解しているかどうかはわかりません。しかし、これに似たものが動作するはずです:

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
于 2012-11-24T22:59:55.303 に答える