Dijkstra算法从邻接矩阵

Question

我具有由2D阵列表示的有向非循环图的邻接矩阵：

[[0, 4, 3, 0] 
[0, 0, 0, 1] 
[0, 3, 0, 1] 
[2, 0, 0, 0]] 

是否有一个Python模块或快速代码段可以在此数据类型运行Dijkstra算法？ Python cookbook使用了一个我相信的优先级字典，但我真的很想将它保存在一个2D数组中。任何帮助，将不胜感激。

Answer 1

networkx可能适合你的需求：

import networkx as nx 
import numpy as np 
A = np.array([[0, 4, 3, 0], 
       [0, 0, 0, 1], 
       [0, 3, 0, 1], 
       [2, 0, 0, 0]]) 
G = nx.from_numpy_matrix(A, create_using=nx.DiGraph()) 
print(nx.dijkstra_path(G, 0, 1)) 

参见：networkx.dijkstra_path