CODEWITHSUNDEEP
pythonnetworkxshortest-path
Mohamed Ibrahim
Mohamed Ibrahim

Reputation: 191

Is there already implemented algorithm in Networkx to return paths lengths along with paths?

I am using shortest_simple_paths() that is implemented in Networkx to find k-shortest/best paths between two nodes. shortest simple paths

However, I also need the algorithm to return the path length of the returned path. I will need the path length based on already configured 'weights' and not based on hop counts. I know this is a simple problem and can be implemented very easily, but I couldn't find one that is already implemented and effective.

Upvotes: 1

Views: 1123

Answers (1)

Kevin
Kevin

Reputation: 8227

It can be achieved by including len(path) in the for loop from the Examples section of shortest_simple_paths.

G = nx.cycle_graph(7)
paths = list(nx.shortest_simple_paths(G, 0, 3))
print(paths)
[[0, 1, 2, 3], [0, 6, 5, 4, 3]]

Modify the edges from the linked example so the shorter path by "hop counts" has a higher cumulative weight than the longer path.

for u,v in G.edges():
    if (all(i < 4 for i in [u,v])):
        G[u][v]['weight'] = 0.75
    else:
        G[u][v]['weight'] = 0.25

Copy the k_shortest_paths function, again from the link.

from itertools import islice
def k_shortest_paths(G, source, target, k, weight=None):
     return list(islice(nx.shortest_simple_paths(G, source, target, weight=weight), k))

Compare the output of k_shortest_paths when weight='weight' and weight=None:

for path in k_shortest_paths(G, 0, 3, 2, weight='weight'):
    print(path, len(path))
([0, 6, 5, 4, 3], 5)
([0, 1, 2, 3], 4)

for path in k_shortest_paths(G, 0, 3, 2, weight=None):
    print(path, len(path))
([0, 1, 2, 3], 4)
([0, 6, 5, 4, 3], 5)

Upvotes: 1

Related Questions