python – 在networkx中定向,加权平衡树导入和最短路径
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 在networkx中定向,加权平衡树导入和最短路径,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1263字,纯文字阅读大概需要2分钟。
内容图文
![python – 在networkx中定向,加权平衡树导入和最短路径](/upload/InfoBanner/zyjiaocheng/803/121949e2765d4cf5b9424e1eb5229efa.jpg)
我有一个平衡的树,分支因子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,找到数字三角形的最大总和.我已经通过memoization递归解决了问题,但我想尝试用Networkx包解决它.)
解决方法:
Is the algorithm choice correct?
是.您可以使用正权重,并调用nx.dijkstra_predecessor_and_distance以获取从根节点0开始的最短路径.
How do I “easily” import this data set into a Networkx graph object?
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 – 在networkx中定向,加权平衡树导入和最短路径全部内容,希望文章能够帮你解决python – 在networkx中定向,加权平衡树导入和最短路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。