贝尔曼-福特负权重 - Networkx

Question

我有一组节点的列表，我想找到最短路径。因为我的节点有负权重，所以我需要用贝尔曼-福特算法。我正在使用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

针对你的问题，如果想要打印出nx.bellman_ford()的路径，可以参考Aric的回答，不过要更新最后一条语句。

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

定义一个函数，把返回的前驱节点转换成路径

def predecessors_to_path(pred, source, target):
    path = []
    curr = target
    while curr != source:
        path.append(curr)
        curr = pred[curr]
    path.append(source)
    path.reverse()
    return path

要获取你的路径形式，只需转换格式即可

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