Dial’s Algorithm
(Graph/ShortestPath/dial.py)

• View this file on GitHub
• Last update: 2021-06-02 23:10:54+09:00

概要

重み付き有向グラフ上で、単一始点最短経路問題を解くアルゴリズム。辺の重みの最大値が小さいときに、高速に動作する。

使い方

dial(graph: Sequence[Sequence[Tuple[int, int]]], start: int, max_w: int) -> List[int]
重み付き有向グラフ graph 上での、 start を始点とした単一始点最短距離の配列を返す。辺の重みの最大値 $W$ を max_w として与えておく。計算量 $O(WV + E)$

Verified with

• TestCase/AOJ/ALDS1_12_B.dial.test.py

Code

def dial(graph, start, max_w):
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    stacks = [[] for i in range(max_w + 1)]
    stacks[0].append(start)
    for d in range(max_w * (n - 1) + 1):
        st = stacks[d % (max_w + 1)]
        while st:
            v = st.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
                    stacks[(d + cost) % (max_w + 1)].append(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