CODEWITHSUNDEEP
pythonpython-3.xnetworkxshortest-pathdijkstra
Sourav Kumar Agarwal
Sourav Kumar Agarwal

Reputation: 73

How to get the weight of the smallest path between two nodes?

I have a networkx graph in Python, with weighted edges. I want to get the weight of the smallest path between two nodes.

Currently, I am getting the nodes in the shortest path from the nx.shortest_path implementation, and then iterating through each pair and summing over the weights between each pair of node.

shortest_path = nx.shortest_path(G, source, destination, 'distance')

#function to iterate over each pair

import itertools
def pairwise(iterable):
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)

weightSum = 0
for adjPair in pairwise(shortest_path):
    weightSum = weightSum + G[adjPair[0]][adjPair[1]]['distance']

Is there a better (built-in) alternative to this?

Upvotes: 2

Views: 2517

Answers (2)

sentence
sentence

Reputation: 8933

You look for single_source_dijkstra:

from networkx.algorithms.shortest_paths.weighted import single_source_dijkstra

single_source_dijkstra(G,s,t)

example

import networkx as nx
from networkx.algorithms.shortest_paths.weighted import single_source_dijkstra

G = nx.Graph()

G.add_edge('a', 'b', weight=0.6)
G.add_edge('a', 'c', weight=6)
G.add_edge('c', 'd', weight=0.1)
G.add_edge('c', 'e', weight=0.7)
G.add_edge('c', 'f', weight=0.9)
G.add_edge('a', 'd', weight=0.3)

single_source_dijkstra(G,'b','f')

output

(1.9, ['b', 'a', 'd', 'c', 'f'])

Upvotes: 4

lazer-guided-lazerbeam
lazer-guided-lazerbeam

Reputation: 254

The networkx documentation has this page: shortest paths.

There are several options, but it looks like shortest_path_length() is what you want.

For clarity:

shortest_path = nx.shortest_path_length(G, source, destination, 'distance')

Upvotes: 0

Related Questions