回答編集履歴
1
例を追加
answer
CHANGED
|
@@ -1,6 +1,7 @@
|
|
|
1
1
|
いわゆる隣接行列表現のグラフで最短経路問題を解きたい、ということですね。
|
|
2
2
|
|
|
3
3
|
Floyd–Warshall algorithm という頂点数をnとしたときにO(n^3)で最短経路を求めるアルゴリズムがあります。
|
|
4
|
-
ソースコードの例: https://yottagin.com/?p=7549
|
|
4
|
+
ソースコードの例: [Python ABC012 D ワーシャルフロイド](https://yottagin.com/?p=7549)
|
|
5
5
|
|
|
6
|
-
ちなみに、Dijkstra algorithm というより高速なアルゴリズムもあります。
|
|
6
|
+
ちなみに、Dijkstra algorithm というより高速なアルゴリズムもあります。
|
|
7
|
+
ソースコードの例: [蟻本 python 単一最短経路法2（ダイクストラ法） 競技プログラミング - じゅっぴーダイアリー](https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%8D%98%E4%B8%80%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%952%EF%BC%88%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95%EF%BC%89_%E7%AB%B6%E6%8A%80%E3%83%97)
|