ダイクストラ法 ($O((E + V)\log V)$) + 経路復元
(Graph/ShortestPath/dijkstra_trace.py)

• View this file on GitHub
• Last update: 2022-01-22 18:47:07+09:00

概要

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

使い方

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

• trace_route(goal: int, parent: List[int]) -> List[int]
  dijkstra 法で求めた経路復元用の配列 parent を用いて、終点 goal までの頂点経路を返す。経路の頂点数を $k$ とすると、計算量 $O(k)$

Verified with

• TestCase/LibraryChecker/shortest_path.test.py

Code

# from heapq import heappop, heappush
from standard_library.heapq import heappop, heappush


def dijkstra(start, graph):
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    parent = [-1] * n
    q = [(0, start)]  # q = [(startからの距離, 現在地)]
    while q:
        d, v = heappop(q)
        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
                parent[nxt_v] = v
                heappush(q, (dist[nxt_v], nxt_v))
    return dist, parent


def trace_route(goal, parent):
    if parent[goal] == -1:
        return []
    path = []
    v = goal
    while v != -1:
        path.append(v)
        v = parent[v]
    return path[::-1]

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