ダイクストラ法 ($O(V^2)$)
(Graph/ShortestPath/dijkstra_v2.py)

• View this file on GitHub
• Last update: 2021-01-05 04:12:38+09:00

概要

重み付き有向グラフにおける単一始点最短経路問題を解くアルゴリズム。

使い方

dijkstra_v2(start: int, matrix: Sequence[Sequence[int]]) -> List[int]
隣接行列 matrix で表現されるグラフ上での、始点 start からすべての頂点への最短距離を求める。計算量 $O(V^2)$

Verified with

• TestCase/AOJ/ALDS1_12_B.test.py

Code

def dijkstra_v2(start, matrix):
    INF = 10 ** 18
    n = len(matrix)
    used = [False] * n
    dist = [INF] * n
    dist[start] = 0
    while True:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or dist[u] < dist[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        for nxt_v in range(n):
            dist[nxt_v] = min(dist[nxt_v], dist[v] + matrix[v][nxt_v])
    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