dijkstra
(expansion/graph/dijkstra.py)

• View this file on GitHub
• Last update: 2023-07-06 22:40:04+09:00

概要

ダイクストラ法です．

$edges[from] = [(to1, cost1), (to2, cost2), …)]$の形式で辺情報を与えてください

使い方

inf は十分に大きい値を適当に設定してください

dist = dijkstra(edges, s=0, inf=1 << 60)

Code

import heapq


def dijkstra(edges, s=0, inf=1 << 60):
    """
    edges[from] = [(to1, cost1), (to2, cost2), ...)]
    """
    n = len(edges)
    dist = [inf] * n
    dist[s] = 0
    hq = [s]
    while hq:
        tmp = heapq.heappop(hq)
        d = tmp // n
        pos = tmp - n * d
        if dist[pos] < d:
            continue
        for npos, c in edges[pos]:
            if dist[npos] > dist[pos] + c:
                dist[npos] = dist[pos] + c
                heapq.heappush(hq, npos + n * dist[npos])

    return dist

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page