如何获取两个节点之间最小路径的权重?
How to get the weight of the smallest path between two nodes?
我在 Python 中有一个带有加权边的 networkx 图。我想获取两个节点之间最小路径的权值。
目前,我正在从 nx.shortest_path 实现中获取最短路径中的节点,然后遍历每一对并对每对节点之间的权重求和。
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']
是否有更好的(内置)替代方案?
networkx 文档有此页面:shortest paths。
有几个选项,但看起来 shortest_path_length()
是您想要的。
为清楚起见:
shortest_path = nx.shortest_path_length(G, source, destination, 'distance')
from networkx.algorithms.shortest_paths.weighted import single_source_dijkstra
single_source_dijkstra(G,s,t)
例子
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')
输出
(1.9, ['b', 'a', 'd', 'c', 'f'])
我在 Python 中有一个带有加权边的 networkx 图。我想获取两个节点之间最小路径的权值。
目前,我正在从 nx.shortest_path 实现中获取最短路径中的节点,然后遍历每一对并对每对节点之间的权重求和。
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']
是否有更好的(内置)替代方案?
networkx 文档有此页面:shortest paths。
有几个选项,但看起来 shortest_path_length()
是您想要的。
为清楚起见:
shortest_path = nx.shortest_path_length(G, source, destination, 'distance')
from networkx.algorithms.shortest_paths.weighted import single_source_dijkstra
single_source_dijkstra(G,s,t)
例子
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')
输出
(1.9, ['b', 'a', 'd', 'c', 'f'])