Python 最短経路問題

Question

Pythonで最短経路問題を解く際にメモ化を行いたい

写真のような状態遷移表において、
動的計画法を用いてメモ化を行いつつ最短経路をもとめたいです。

遷移の際のコストはcsvファイルから読み取り、
12行12列の二次元配列に格納します。
例:Sから1へ遷移する際には配列の[0][1]のコスト、1から4へ遷移する際には[1][4]のコスト

どういったソースコードが適切なのか教えていただきたいです。

Comments

[tiitoi]

ダイキストラ法で調べましたか？

[sho8065]

1度ダイクストラ法を調べて書いたソースコードを教授に提出したところ、
動的計画法を行えてないと言われました。

Answer 1

いわゆる隣接行列表現のグラフで最短経路問題を解きたい、ということですね。

Floyd–Warshall algorithm という頂点数をnとしたときにO(n^3)で最短経路を求めるアルゴリズムがあります。
ソースコードの例: Python ABC012 D ワーシャルフロイド

ちなみに、Dijkstra algorithm というより高速なアルゴリズムもあります。
ソースコードの例: 蟻本　python 単一最短経路法2（ダイクストラ法）　競技プログラミング - じゅっぴーダイアリー