CODEWITHSUNDEEP
pythonnetworkx
SharpObject
SharpObject

Reputation: 607

How to specify edge length in Networkx for calculating shortest distance?

I have a list of nodes and edges but I want some edges to be of length two instead of one. So when the distance between the nodes is calculated using the built in algorithm it returns

For example, if I have (1, 2), (2*, 3), (4*, 5) as edges between nodes, where the distance between the nodes with an asterisk have length two, the distance between (1, 2) should be 1, (2,3) should be 2 instead of 1 and then the distance between (1,5) should be 5 instead of 3.

When adding nodes I've tried G.add_edge(4,5,length=2) but nx.shortest_path_length(G,source=4,target=5)) still returns 1 instead of two. How can I specify edge length?

Upvotes: 5

Views: 9757

Answers (1)

Marius
Marius

Reputation: 60070

You need to have a length attribute attached to your edges, and then specify that you want to weight by those lengths when finding the shortest path:

# Had to add an edge from 3 to 4 to your example edges
#   or there's no path from 1 to 5
edges = [(1, 2, 1), (2, 3, 2), (3, 4, 1), (4, 5, 2)]

G = networkx.Graph()

for start, end, length in edges:
    # You can attach any attributes you want when adding the edge
    G.add_edge(start, end, length=length)

networkx.shortest_path_length(G, 1, 5, weight='length')
Out[8]: 6

Note that the name of the attribute doesn't have to be length, it could have some other name, such as weight, len, or whatever your preference is.

Upvotes: 10

Related Questions