有没有在Networkx中实现返回路径长度的算法？

Question

我使用Networkx中实现的shortest_simple_paths（）来查找两个节点之间的k-最短/最佳路径。 shortest simple paths

但是，我还需要算法来返回返回路径的路径长度。我需要基于已经配置的'权重'的路径长度，而不是基于跳跃计数。我知道这是一个简单的问题，可以很容易地实现，但我找不到一个已经实现并有效的问题。在

Answer 1

它可以通过在来自Examples section of ^{}的for循环中包含len(path)来实现。在

G = nx.cycle_graph(7)
paths = list(nx.shortest_simple_paths(G, 0, 3))
print(paths)
[[0, 1, 2, 3], [0, 6, 5, 4, 3]]

修改链接示例中的边，使“hop counts”的较短路径比较长的路径具有更高的累积weight。在

^{pr2}$

再次从链接复制k_shortest_paths函数。在

from itertools import islice
def k_shortest_paths(G, source, target, k, weight=None):
     return list(islice(nx.shortest_simple_paths(G, source, target, weight=weight), k))

比较k_shortest_paths在weight='weight'和weight=None时的输出：

for path in k_shortest_paths(G, 0, 3, 2, weight='weight'):
    print(path, len(path))
([0, 6, 5, 4, 3], 5)
([0, 1, 2, 3], 4)

for path in k_shortest_paths(G, 0, 3, 2, weight=None):
    print(path, len(path))
([0, 1, 2, 3], 4)
([0, 6, 5, 4, 3], 5)