Networkx中是否已经实现了算法来返回路径长度以及路径? [英] Is there already implemented algorithm in Networkx to return paths lengths along with paths?

问题描述

我正在使用在Networkx中实现的shortest_simple_paths()来查找两个节点之间的k最短/最佳路径. 最短的简单路径

I am using shortest_simple_paths() that is implemented in Networkx to find k-shortest/best paths between two nodes. shortest simple paths

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

However, I also need the algorithm to return the path length of the returned path. I will need the path length based on already configured 'weights' and not based on hop counts. I know this is a simple problem and can be implemented very easily, but I couldn't find one that is already implemented and effective.

推荐答案

可以通过在

It can be achieved by including len(path) in the for loop from the Examples section of shortest_simple_paths.

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

修改链接示例中的边，使较短的路径(跳数")的累积weight高于较长的路径.

Modify the edges from the linked example so the shorter path by "hop counts" has a higher cumulative weight than the longer path.

for u,v in G.edges():
    if (all(i < 4 for i in [u,v])):
        G[u][v]['weight'] = 0.75
    else:
        G[u][v]['weight'] = 0.25

再次从链接复制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))

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

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)

这篇关于Networkx中是否已经实现了算法来返回路径长度以及路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！