CODEWITHSUNDEEP
pythongraphnetworkx
Andrés Aguilar
Andrés Aguilar

Reputation: 21

Bellman Ford Negative Weight - Networkx

I have this list of nodes, and I want to get the minimum path, as I have nodes with negative weight would have to use Bellman Ford, I am using networkx library, however I did not get the form to print the path, this is the list of nodes with weights and the command that I am using

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)

Where G_Bellman_Ford is the graph

Upvotes: 2

Views: 1986

Answers (2)

Jesse
Jesse

Reputation: 3393

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)

Define function to convert return predecessors to path

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

To get your path form, just convert format

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

Upvotes: 0

Aric
Aric

Reputation: 25289

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

Upvotes: 1

Related Questions