вычисление веса графика в Python с помощью NetworkX

Я использую networkx для вычисления кратчайшего расстояния (с точки зрения веса) между двумя вершинами в ориентированном взвешенном графе. Я думаю, что отношение алгоритм dijkstra_path_length является правильным для использования здесь, но я не понимаю, что я должен поставить в качестве параметра по умолчанию для веса, чтобы получить желаемые результаты.

import networkx as nx
G = nx.MultiDiGraph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
G.add_edge('A', 'B', 5)
G.add_edge('B', 'C', 4)
G.add_edge('C', 'D', 8)
G.add_edge('D', 'C', 8)
G.add_edge('D', 'E', 6)
G.add_edge('A', 'D', 5)
G.add_edge('C', 'E', 2)
G.add_edge('E', 'B', 3)
G.add_edge('A', 'E', 7)

Вот график, который я ввел. Мне нужно вычислить кратчайший путь (с точки зрения веса) от A до C (его ABC с весом = 9), но что бы я ни делал, единственный ответ, который я получаю, - 2 (количество ребер, как будто граф не имеет веса) . Правильный ответ должен быть 9.


python graph networkx dijkstra
person Anton Atanasov    schedule 11.06.2015    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Проблема в том, что вам нужно написать слово «вес», чтобы присвоить его ребру. Вы даете метки краям, но не весу.

Следующий код работает с выводом 9, когда вы вычисляете расстояние между узлами A и C.

import networkx as nx
G = nx.MultiDiGraph()
G.add_nodes_from(['A', 'B', 'C', 'D', 'E'])

G.add_edge('A', 'B', weight=5)
G.add_edge('B', 'C', weight=4)
G.add_edge('C', 'D', weight=8)
G.add_edge('D', 'C', weight=8)
G.add_edge('D', 'E', weight=6)
G.add_edge('A', 'D', weight=5)
G.add_edge('C', 'E', weight=2)
G.add_edge('E', 'B', weight=3)
G.add_edge('A', 'E', weight=7)

print nx.dijkstra_path_length(G, source = 'A', target = 'C')
person ivangtorre    schedule 11.06.2015

arrow_upward
0
arrow_downward

Удалите эту строку из своего кода

G.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
person Shantanu Deshpande    schedule 11.06.2015

arrow_upward
0
arrow_downward

может быть, вы можете попробовать использовать nx.shortest_path ()

person Jing    schedule 29.10.2020