如何使用 NetworkX 获得加权图中的最短路径？
How to get the shortest path in a weighted graph with NetworkX?
我试图在定义为
的加权图中获得最短路径
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)
预期答案是 131,201,96，因为对于该路径，我的权重总和最少。我得到的是 131,673,96。我尝试更改权重，但显然 shortest_path 总是 returns 最长 路径。怎么回事？
来自 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’,
（强调我的）
如果您没有明确声明要查找最短加权路径（通过指定 weight 参数），则所有权重均取为一个。
要解决您的问题，请执行以下操作：
print(nx.shortest_path(g,source=131,target=96, weight='weight'))
输出：
[131, 201, 96]
我试图在定义为
的加权图中获得最短路径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)
预期答案是 131,201,96，因为对于该路径，我的权重总和最少。我得到的是 131,673,96。我尝试更改权重，但显然 shortest_path 总是 returns 最长 路径。怎么回事？
来自 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’,
（强调我的）
如果您没有明确声明要查找最短加权路径（通过指定 weight 参数），则所有权重均取为一个。
要解决您的问题，请执行以下操作：
print(nx.shortest_path(g,source=131,target=96, weight='weight'))
输出：
[131, 201, 96]