所有使用networkx的加权图的最短路径？ [英] All shortest paths for weighted graphs with networkx?

问题描述

我有一个由两组不同的边组成的图。第一组是由权重1（列表1）的边缘制成的。第二组由权重2（列表2）的边缘构成。首先，我使用networkx创建图形，然后使用add_edges_from添加列表1和列表2.我想计算此加权图形中的所有最短路径。基本上，我正在寻找类似于all_shortest_paths的权重（看起来像dijkstra模块不允许你知道给定源和给定目标之间的所有可能路线）。如果我尝试使用加权链接（3元组，两个节点和权重）的all_shortest_path，我会得到错误。有谁能够帮助我？
非常感谢！

I have a graph composed by two different sets of edges. The first set is made by edges of weight 1 (list 1). The second set is made by edges of weight 2 (list 2). First, I create the graph with networkx and then use add_edges_from to add list 1 and list 2. I would like to compute all the shortest paths in this weighted graph. Basically I'm looking for the analogous of "all_shortest_paths" but with weights (looks like "dijkstra" module does not allow you to know all the possible routes between a given source and a given target). If I try to use "all_shortest_path" with weighted links (3-tuples, the two nodes and the weight) I get the error . Can anybody help me? Thanks a lot!

推荐答案

下面是一个简单的例子，展示了如何使用all_shortest_paths（） b
$ b

Here is a simple example to show how all_shortest_paths() works

import networkx as nx
import StringIO
edges = StringIO.StringIO("""
a b 1
a bb 1
b c 2
bb c 2
c d 1
a d 10""")
G = nx.read_weighted_edgelist(edges, nodetype=str)
print list(nx.all_shortest_paths(G, 'a', 'd', weight='weight'))
# [['a', 'b', 'c', 'd'], ['a', 'bb', 'c', 'd']]

这篇关于所有使用networkx的加权图的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！