GRL_1_C: All Pairs Shortest Path (続き2)
解説を読む
ワーシャルフロイドのアルゴリズムというらしい
レナの本には名前しか出てないみたいだ
レナの本は索引がないのがよろしくないな
やってることはそっくり・・・かな?
いや?
3重にループしただけで終わってる?
それでいいの?
一発で全部最短になる?
ていうか
形は一番外側のループがtoを回すループになってるだけで
不思議なほど似てるけど
考え方が全然違ってる
経由する点をひとつずつ増やしていく、という考え方だった
オーダはとてもわかりやすく3乗だな 3乗でよかったんだ
自分のコードは3乗の周りにもうひとつループがあったな
嘘ついてましたすみません
ではコード修正
修正したところだけ
def get_shortest_paths(D):
n = len(D)
for to in range(n):
for fr in range(n):
here = D[fr][to]
if here == INF:
continue
for to2 in range(n):
here2 = D[to][to2]
if here2 == INF:
continue
D[fr][to2] = min(D[fr][to2], here + here2)
def main():
D = read_adj_mat()
get_shortest_paths(D)
for d in [D[x][x] for x in range(len(D))]:
if d < 0:
print("NEGATIVE CYCLE")
break
else:
print_result(D)
昨日のコードで一番重かったのはCase#46
頂点100個でエッジが9900個のやつ
時間は1.64sで使用メモリが7056KB
今回は0.53sで6344KB
完敗です