我有一个平衡树,分支因子为 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 算法来完成。
  • 算法选择是否正确?
  • 如何“轻松”将此数据集导入 Networkx 图形对象?

  • (PS:这是 Euler Problem 67 项目,在一个数字三角形中找到最大和。我已经用记忆化的递归解决了这个问题,但我想尝试用 Networkx 包来解决它。)

    最佳答案



    是的。您可以使用正权重,并调用 nx.dijkstra_predecessor_and_distance 以获取从根节点 0 开始的最短路径。


    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()
    

    关于python - 网络x中的定向加权平衡树导入和最短路径,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13546064/

    10-16 02:40