Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 897
SharpObject Avatar asked Jan 07 '23 03:01

SharpObject


1 Answers

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.

like image 171
Marius Avatar answered Jan 23 '23 02:01

Marius