Есть ли у networkx функция для расчета длины пути с учетом весов? - PullRequest
Новая
       108

Есть ли у networkx функция для расчета длины пути с учетом весов?

2 голосов
/ 19 июня 2019

Я работаю с networkx для вычисления k-кратчайших простых путей . nx.shortest_simple_paths(G, source, target, weight=weight) возвращает список путей в порядке возрастания стоимости (суммарная длина пути с учетом весов).

Я заинтересован в получении стоимости этих путей. Есть ли в 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
--------------

1 Ответ

0 голосов
/ 19 июня 2019

Очевидно, что функция k_shortest_path еще не была реализована в NetworkX, хотя требование не является новым, и вы могли найти некоторую попытку реализации алгоритма Йены в Интернете .

(очень) грубое решение вашего вопроса может быть: 

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)

enter image description here

вызов: 

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

возвращается: 

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