CODEWITHSUNDEEP
pythongraphnetworkxshortest-path
abhay
abhay

Reputation: 87

How to get the shortest path in a weighted graph with NetworkX?

I'm trying to get the shortest path in a weighted graph defined as

import networkx as nx
import matplotlib.pyplot as plt
g = nx.Graph()
g.add_edge(131,673,weight=673)
g.add_edge(131,201,weight=201)
g.add_edge(673,96,weight=96)
g.add_edge(201,96,weight=96)
nx.draw(g,with_labels=True,with_weight=True)
plt.show()

to do so I use

nx.shortest_path(g,source=131,target=96)

The expected answer is 131,201,96 because for that path I have the least sum of weights. I'm getting 131,673,96 instead. I tried changing the weights but shortest_path always returns the longest path apparently. What is going on?

Upvotes: 5

Views: 21523

Answers (1)

warped
warped

Reputation: 9481

from the documentation of nx.shortest_path:

shortest_path(G, source=None, target=None, weight=None, method='dijkstra')[source]
Compute shortest paths in the graph.

Parameters
G (NetworkX graph)

source (node, optional) – Starting node for path. If not specified, compute shortest paths for each possible starting node.

target (node, optional) – Ending node for path. If not specified, compute shortest paths to all possible nodes.

> weight (None or string, optional (default = None)) – If None, every edge has weight/distance/cost 1. If a string, use this edge attribute as the edge weight. Any edge attribute not present defaults to 1.

method (string, optional (default = ‘dijkstra’)) – The algorithm to use to compute the path. Supported options: ‘dijkstra’,

(emphasis mine)

If you do not explictly state that you want to find the shortest weighted path (by specifying the weightargument), all weights are taken to be one.

To fix your problem, do:

print(nx.shortest_path(g,source=131,target=96, weight='weight'))

output:

[131, 201, 96]

Upvotes: 17

Related Questions