Использование dijkstra_path функции в библиотеке NetworkX

Question

Я использую networkx библиотеку, чтобы найти кратчайший путь между двумя узлами, используя dijkstra Algo следующего

import networkx as nx 

A = [[0, 100, 0, 0 , 40, 0], 
    [100, 0, 20, 0, 0, 70], 
    [0, 20, 0, 80, 50, 0], 
    [0, 0, 80, 0, 0, 30], 
    [40, 0, 50, 0, 0, 60], 
    [0, 70, 0, 30, 60, 0]]; 

print(nx.dijkstra_path(A, 0, 4)) 

В приведенной выше коде я использую матрицу непосредственно, но библиотека требует графика для создаются следующим образом:

G = nx.Graph() 
G = nx.add_node(<node>) 
G.add_edge(<node 1>, <node 2>) 

Это очень трудоемкий процесс создания матрицы с использованием вышеуказанных команд. Есть ли способ дать ввод как взвешенную матрицу функции dijkstra_path.

Answer 1

Сначала вам нужно преобразовать матрицу смежности в матрицу numpy с np.array. Тогда вы можете просто создать свой график с помощью from_numpy_matrix.

import networkx as nx 
import numpy as np 

A = [[0, 100, 0, 0 , 40, 0], 
    [100, 0, 20, 0, 0, 70], 
    [0, 20, 0, 80, 50, 0], 
    [0, 0, 80, 0, 0, 30], 
    [40, 0, 50, 0, 0, 60], 
    [0, 70, 0, 30, 60, 0]] 

a = np.array(A) 
G = nx.from_numpy_matrix(a) 

print(nx.dijkstra_path(G, 0, 4)) 

Выход:

[0, 4] 

Side Примечание: Вы можете проверить ребра графа с помощью следующего кода.

for edge in G.edges(data=True): 
    print(edge) 

Выход:

(0, 1, {'weight': 100}) 
(0, 4, {'weight': 40}) 
(1, 2, {'weight': 20}) 
(1, 5, {'weight': 70}) 
(2, 3, {'weight': 80}) 
(2, 4, {'weight': 50}) 
(3, 5, {'weight': 30}) 
(4, 5, {'weight': 60})