如何使用NetworkX获得加权图中的最短路径? [英] 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()
为此我使用
nx.shortest_path(g,source=131,target=96)
期望的答案是13120196,因为对于该路径,我的权重总和最小.我得到的是131,673,96.我尝试更改权重,但是shortest_path
总是总是明显地返回最长路径.发生了什么事?
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?
推荐答案
. generic.shortest_path.html#networkx.algorithms.shortest_paths.generic.shortest_path"rel =" nofollow noreferrer> nx.shortest_path的文档:
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.
>体重 (无或字符串,可选(默认=无))–如果为无,则每个边缘的权重/距离/成本为1.如果为字符串,则使用此边缘 属性作为边缘权重.任何不存在的边属性默认 到1.
> 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’,
(重点是我的)
如果未明确指出要找到最短的加权路径(通过指定weight
参数),则所有权重均视为1.
If you do not explictly state that you want to find the shortest weighted path (by specifying the weight
argument), all weights are taken to be one.
要解决您的问题,请执行以下操作:
To fix your problem, do:
print(nx.shortest_path(g,source=131,target=96, weight='weight'))
输出:
[131, 201, 96]
这篇关于如何使用NetworkX获得加权图中的最短路径?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!