CODEWITHSUNDEEP
pythonpython-3.xnetworkxshortest-pathweighted-graph
PPR
PPR

Reputation: 417

Does networkx has a function to calculate the length of the path considering weights?

I am working with networkx to calculate the k-shortest simple paths. nx.shortest_simple_paths(G, source, target, weight=weight) returns the list of paths in the increasing order of cost (cumulative path length considering weights).

I am interested in obtaining the cost of these paths. Is there any simple function in networkX to obtain this?

This question is similar to this question: Is there already implemented algorithm in Networkx to return paths lengths along with paths?.

I believe the posted answer in that post is wrong. From How to add custom function for calculating edges weights in a graph? I made the following solution (see below).

Is this the right approach?

Is there anything simple available in the networkx library?

My aim is to find the cost of k-shortest path.

G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
G.add_edge('a', 'b', weight=2)
G.add_edge('b', 'c', weight=4)
G.add_edge('a', 'c', weight=10)
G.add_edge('c', 'd', weight=6)
G.size()

def path_length(G, nodes, weight):
    w = 0
    for ind,nd in enumerate(nodes[1:]):
        prev = nodes[ind]
        w += G[prev][nd][weight]
    return w

for path in nx.shortest_simple_paths(G, 'a', 'd', weight='weight'):
    print(path, len(path)) # wrong approach
    print(path, path_length(G,path,'weight')) # correct solution
    print("--------------")

This will output this:

['a', 'b', 'c', 'd'] 4
['a', 'b', 'c', 'd'] 12
--------------
['a', 'c', 'd'] 3
['a', 'c', 'd'] 16
--------------

Upvotes: 6

Views: 12182

Answers (3)

nbeuchat
nbeuchat

Reputation: 7091

You can use path_weight(G, path, weight="weight") as follow:

from networkx.algorithms.shortest_paths.generic import shortest_path
from networkx.classes.function import path_weight

path = shortest_path(G, source=source, target=target, weight="weight")
path_length = path_weight(G, path, weight="weight")

Upvotes: 4

RookieScientist
RookieScientist

Reputation: 313

I appreciate @sentence's and @nbeuchat's solution. However, if you have a large graph @sentence's solution takes so much time and nbeuchat's solution doesn't provide k-shortest paths. I merge their solutions to come up with much faster k-shortest simple paths with path length.

import networkx as nx

G = nx.Graph()

G.add_edge('a', 'b', weight=2)
G.add_edge('b', 'c', weight=4)
G.add_edge('a', 'c', weight=10)
G.add_edge('c', 'd', weight=6)
G.add_edge('b', 'd', weight=2)
G.add_edge('b', 'e', weight=5)
G.add_edge('e', 'f', weight=8)
G.add_edge('d', 'f', weight=8)

from itertools import islice
from networkx.classes.function import path_weight

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

for path in k_shortest_paths(G, 'a','f', 3):
    print(path, path_weight(G, path, weight="weight"))

Upvotes: 5

sentence
sentence

Reputation: 8913

Apparently, a k_shortest_path function has not yet been implemented in NetworkX, even though the demand is not new and you could find some attempt of implementing Yen's algorithm on the web.

A (very) rough solution to your question could be:

def k_shortest_path(G, source, target, k):
    def path_cost(G, path):
        return sum([G[path[i]][path[i+1]]['weight'] for i in range(len(path)-1)])
    return sorted([(path_cost(G,p), p) for p in nx.shortest_simple_paths(G, source,target,weight='weight') if len(p)==k])[0]

For this kind of graph:

import networkx as nx

G = nx.Graph()

G.add_edge('a', 'b', weight=2)
G.add_edge('b', 'c', weight=4)
G.add_edge('a', 'c', weight=10)
G.add_edge('c', 'd', weight=6)
G.add_edge('b', 'd', weight=2)
G.add_edge('b', 'e', weight=5)
G.add_edge('e', 'f', weight=8)
G.add_edge('d', 'f', weight=8)

enter image description here

calling:

k_shortest_path(G, 'a', 'f', 4)

returns:

(12, ['a', 'b', 'd', 'f'])

Upvotes: 2

Related Questions