Направленный, взвешенный импорт сбалансированного дерева и кратчайший путь в networkx

У меня есть сбалансированное дерево с коэффициентом ветвления 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.

  1. Правильно ли выбран алгоритм?
  2. Как «легко» импортировать этот набор данных в объект графа Networkx?

(PS: это задача 67 проекта Euler, поиск максимальной суммы в треугольнике чисел. Я решил вопрос с рекурсией с мемоизацией, но хочу попробовать решить его с помощью пакета Networkx.)


python networkx
person luffe    schedule 24.11.2012    source источник
comment
Я не знаком с Networkx, но если память не изменяет, алгоритм Дейкстры требует неотрицательных весов ребер.   -  person StoryTeller - Unslander Monica    schedule 25.11.2012

Ответы (2)


arrow_upward
4
arrow_downward

Правильно ли выбран алгоритм?

да. Вы можете использовать положительные веса и вызвать 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()
person unutbu    schedule 24.11.2012

arrow_upward
3
arrow_downward

Я не уверен, что понимаю формат ввода. Но что-то похожее на это должно работать:

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
person Aric    schedule 24.11.2012