Как получить вес наименьшего пути между двумя узлами?

У меня есть граф networkx на Python со взвешенными ребрами. Я хочу получить вес наименьшего пути между двумя узлами.

В настоящее время я получаю узлы кратчайшего пути из реализации nx.shortest_path, а затем перебираю каждую пару и суммирую веса между каждой парой узлов.

shortest_path = nx.shortest_path(G, source, destination, 'distance')

#function to iterate over each pair

import itertools
def pairwise(iterable):
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)

weightSum = 0
for adjPair in pairwise(shortest_path):
    weightSum = weightSum + G[adjPair[0]][adjPair[1]]['distance']

Есть ли лучшая (встроенная) альтернатива этому?


python-3.x python shortest-path networkx dijkstra
person Sourav Kumar Agarwal    schedule 25.05.2019    source источник
comment
Что вы подразумеваете под наименьшим путем? Путь с минимальным количеством ребер? Путь с наименьшим весом?   -  person sentence    schedule 26.05.2019
comment
Я думаю, что кратчайший путь с использованием Джикстры дает путь с наименьшим весом. Я хочу знать этот вес.   -  person Sourav Kumar Agarwal    schedule 26.05.2019

Ответы (2)


arrow_upward
3
arrow_downward

Вы ищете _1 _ :

from networkx.algorithms.shortest_paths.weighted import single_source_dijkstra

single_source_dijkstra(G,s,t)

пример

import networkx as nx
from networkx.algorithms.shortest_paths.weighted import single_source_dijkstra

G = nx.Graph()

G.add_edge('a', 'b', weight=0.6)
G.add_edge('a', 'c', weight=6)
G.add_edge('c', 'd', weight=0.1)
G.add_edge('c', 'e', weight=0.7)
G.add_edge('c', 'f', weight=0.9)
G.add_edge('a', 'd', weight=0.3)

single_source_dijkstra(G,'b','f')

вывод

(1.9, ['b', 'a', 'd', 'c', 'f'])
person sentence    schedule 26.05.2019

arrow_upward
0
arrow_downward

В документации networkx есть эта страница: кратчайшие пути.

Есть несколько вариантов, но похоже, shortest_path_length() это то, что вам нужно.

Для ясности:

shortest_path = nx.shortest_path_length(G, source, destination, 'distance')
person lazer-guided-lazerbeam    schedule 25.05.2019