networkx是否有一个函数来计算考虑权重的路径长度？

Question

我正在使用networkx计算k最短的简单路径。nx.shortest_simple_paths（G，源，目标，权重=权重）返回成本递增顺序的路径列表（考虑权重的累积路径长度）。

我有兴趣获得这些路径的成本。networkX中是否有任何简单的函数来获得这个？

这个问题类似于这个问题：Networkx中是否已经实现了返回路径长度和路径的算法？。

我相信在那篇帖子里贴出的答案是错误的。如何添加自定义函数来计算图形中的边权重？我提出了以下解决方案（见下文）。

这是正确的方法吗？

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
--------------

Answer 1

您可以使用path\u weight（G，path，weight=“weight”）如下所示：

from networkx.algorithms.shortest_paths.generic import shortest_path
from networkx.classes.function import path_weight

path = shortest_path(G, source=source, target=target, weight="weight")
path_length = path_weight(G, path, weight="weight")

Answer 2

显然，NetworkX中尚未实现k_最短路径功能，尽管需求并不新鲜，您可以在web上找到一些实现Yen算法的尝试。

您的问题的（非常）粗略的解决方案可以是：

def k_shortest_path(G, source, target, k):
    def path_cost(G, path):
        return sum([G[path[i]][path[i+1]]['weight'] for i in range(len(path)-1)])
    return sorted([(path_cost(G,p), p) for p in nx.shortest_simple_paths(G, source,target,weight='weight') if len(p)==k])[0]

对于此类图形：

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)

打电话：

k_shortest_path(G, 'a', 'f', 4)

返回：

(12, ['a', 'b', 'd', 'f'])

Answer 3

我感谢@SENTION和@nbeuchat的解决方案。然而，如果你有一个大的图，@SENTION的解决方案需要花费很多时间，而nbeuchat的解决方案不提供k-最短路径。我合并了他们的解决方案，得到了更快的具有路径长度的k-最短简单路径。

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"))