从邻接矩阵实现Dijkstra算法

Question

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

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

请问有没有什么Python模块或者简单的代码片段可以在这种数据类型上运行Dijkstra算法？我记得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