贝尔曼福特负重网络

Question

我有这个节点列表，我想得到最小路径，因为我有负权重的节点必须使用Bellman Ford，我正在使用networkx库，但是我没有得到打印路径的表单，这是有权重的节点列表和我正在使用的命令

1 10 {'weight': 96}
1 13 {'weight': 97}
2 11 {'weight': -70}
2 13 {'weight': 77}
3 12 {'weight': 30}
3 13 {'weight': -30}
4 10 {'weight': 17}
4 14 {'weight': -75}
5 11 {'weight': -4}
5 14 {'weight': 45}
6 12 {'weight': -67}
6 14 {'weight': 63}
7 10 {'weight': 38}
7 15 {'weight': -40}
8 11 {'weight': -30}
8 15 {'weight': -46}
9 12 {'weight': 37}
9 15 {'weight': -97}




assert_raises(nx.NetworkXUnbounded,nx.bellman_ford,G_Bellman_Ford,1)

图中G嫒Bellman_Ford是图

Answer 1

For your question, to print the path from nx.bellman_ford(), just follow the answer from Aric, but update last statement.

pred, dist = nx.bellman_ford(G,1)

定义将返回前置任务转换为路径的函数

^{pr2}$

To get your path form, just convert format

>>> print(predecessors_to_path(pred,1,10))
[1, 10]        

Answer 2

In [1]: import networkx as nx

In [2]: edges ="""1 10 {'weight': 96}
1 13 {'weight': 97}
2 11 {'weight': -70}
2 13 {'weight': 77}
3 12 {'weight': 30}
3 13 {'weight': -30}
4 10 {'weight': 17}
4 14 {'weight': -75}
5 11 {'weight': -4}
5 14 {'weight': 45}
6 12 {'weight': -67}
6 14 {'weight': 63}
7 10 {'weight': 38}
7 15 {'weight': -40}
8 11 {'weight': -30}
8 15 {'weight': -46}
9 12 {'weight': 37}
9 15 {'weight': -97}"""

In [3]: lines = edges.split('\n')

In [4]: G = nx.parse_edgelist(lines, nodetype = int, create_using=nx.DiGraph())

In [5]: nx.bellman_ford(G,1)
Out[5]: ({1: None, 10: 1, 13: 1}, {1: 0, 10: 96, 13: 97})