python - 邻接矩阵中的 Dijkstra 算法

Question

我有一个由二维数组表示的有向无环图的邻接矩阵：

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

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

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