ダイクストラ法 (Radix Heap)
(Graph/ShortestPath/dijkstra_radix.py)

• View this file on GitHub
• Last update: 2021-02-02 20:30:49+09:00

概要

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

使い方

dijkstra(start: int, graph: Sequence[Iterable[Tuple[int, int]]], LIMIT: int = 1<<64) -> List[int]
$G = (V, E)$ で表される重み付き有向グラフ graph に対して、start を始点とした単一始点最短距離の配列を返す。計算量 $O((E + V)\log \mathrm{LIMIT})$

Depends on

• Radix Heap (DataStructure/Heap/RadixHeap.py)

Verified with

• TestCase/AOJ/GRL_1_A.RadixHeap.test.py

Code

from DataStructure.Heap.RadixHeap import RadixHeap


def dijkstra(start, graph, LIMIT=1<<64):
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    rh = RadixHeap(LIMIT)
    rh.push(0, start)
    while rh:
        d, v = rh.pop()
        if dist[v] < d:
            continue
        for nxt_v, cost in graph[v]:
            if dist[v] + cost < dist[nxt_v]:
                dist[nxt_v] = dist[v] + cost
                rh.push(dist[nxt_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