我正在与 networkx 一起计算 k-最短简单路径 . nx.shortest_simple_paths(G, source, target, weight=weight)
以成本递增的顺序返回路径列表(考虑权重的累积路径长度)。
我有兴趣获得这些路径的成本。 networkX 中是否有任何简单的函数来获得它?
这个问题类似于这个问题:Is there already implemented algorithm in Networkx to return paths lengths along with paths? .
我相信该帖子中发布的答案是错误的。来自 How to add custom function for calculating edges weights in a graph?我做了以下解决方案(见下文)。
这是正确的方法吗?
networkx 库中有什么简单可用的东西吗?
我的目标是找到 的成本k-最短路径 .
G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
G.add_edge('a', 'b', weight=2)
G.add_edge('b', 'c', weight=4)
G.add_edge('a', 'c', weight=10)
G.add_edge('c', 'd', weight=6)
G.size()
def path_length(G, nodes, weight):
w = 0
for ind,nd in enumerate(nodes[1:]):
prev = nodes[ind]
w += G[prev][nd][weight]
return w
for path in nx.shortest_simple_paths(G, 'a', 'd', weight='weight'):
print(path, len(path)) # wrong approach
print(path, path_length(G,path,'weight')) # correct solution
print("--------------")
这将输出:
['a', 'b', 'c', 'd'] 4
['a', 'b', 'c', 'd'] 12
--------------
['a', 'c', 'd'] 3
['a', 'c', 'd'] 16
--------------
最佳答案
我很欣赏 @sentence 和 @nbeuchat 的解决方案。但是,如果您有一个大图,@sentence 的解决方案会花费很多时间,而 nbeuchat 的解决方案不提供 k 最短路径。我合并了他们的解决方案,以提出更快的具有路径长度的 k-shortest 简单路径。
import networkx as nx
G = nx.Graph()
G.add_edge('a', 'b', weight=2)
G.add_edge('b', 'c', weight=4)
G.add_edge('a', 'c', weight=10)
G.add_edge('c', 'd', weight=6)
G.add_edge('b', 'd', weight=2)
G.add_edge('b', 'e', weight=5)
G.add_edge('e', 'f', weight=8)
G.add_edge('d', 'f', weight=8)
from itertools import islice
from networkx.classes.function import path_weight
def k_shortest_paths(G, source, target, k, weight=None):
return list(islice(nx.shortest_simple_paths(G, source, target, weight='weight'), k))
for path in k_shortest_paths(G, 'a','f', 3):
print(path, path_weight(G, path, weight="weight"))
关于python - networkx 是否具有计算权重的路径长度的功能?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56657088/