python - 隣接行列からのダイクストラのアルゴリズム

Question

2D 配列で表される有向非巡回グラフの隣接行列があります。

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

このデータ型で Dijkstra のアルゴリズムを実行できる Python モジュールまたは簡単なコード スニペットはありますか? Python のクックブックでは優先度の高い辞書が使用されていると思いますが、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