ワーシャルフロイド法
(Graph/ShortestPath/warshall_floyd.py)

• View this file on GitHub
• Last update: 2021-01-15 11:26:51+09:00

概要

重み付き有向グラフにおける全点対最短距離問題を解くアルゴリズム。各辺の重みは負でもよい。

使い方

warshall_floyd(matrix: Sequence[Sequence[int]]) -> List[List[int]]
隣接行列 matrix で表現されるグラフ上での、全点対最短距離の配列を返す。計算量 $O(V^3)$

備考

• 頂点 $u$ が負閉路に含まれるとき、$u$ - $u$ 間の最短距離 distance[u][u] が負になる。
• ある辺を既存の辺より小さいコストの辺に変更するとき、$O(V^2)$ で更新ができる。ARC035-C

Verified with

• TestCase/AOJ/GRL_1_C.test.py

Code

def warshall_floyd(matrix):
    n = len(matrix)
    dist = [[d for d in row] for row in matrix]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page