Есть ли уже реализованный алгоритм в Networkx для возврата длины пути вместе с путями?

Question

Я использую shorttest_simple_paths (), который реализован в Networkx, чтобы найти k-кратчайшие / лучшие пути между двумя узлами. кратчайшие простые пути

Однако мне также нужен алгоритм для возврата длины пути возвращаемого пути.Мне понадобится длина пути на основе уже настроенных «весов», а не на основе количества переходов.Я знаю, что это простая проблема, и ее можно реализовать очень легко, но я не смог найти ту, которая уже реализована и эффективна.

Answer 1

Этого можно добиться, включив len(path) в цикл for из раздела Примеры в 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, чем более длинный путь.

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

Сравнитевывод 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)