01-BFS
(Graph/ShortestPath/bfs01.py)

View this file on GitHub
Last update: 2022-01-22 12:11:49+09:00

概要

各辺の長さが $0$ または $1$ の有向グラフ上で、単一始点最短経路問題を解くアルゴリズム。

使い方

bfs(graph: Sequence[Sequence[Tuple[int, int]]], start: int) -> List[int]
重み付き有向グラフ graph 上での、 start を始点とした単一始点最短距離の配列を返す。ただし、重みは $0$ または $1$ のどちらかでなければならないことに注意。計算量 $O(V + E)$

参考

・01-BFSのちょっと丁寧な解説 - ARMERIA

Code

# from collections import deque
from standard_library.collections import deque


def bfs01(graph, start):
    INF = 10 ** 18
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    que = deque([start])
    while que:
        v = que.popleft()
        for nxt_v, cost in graph[v]:
            d = dist[v] + cost
            if d < dist[nxt_v]:
                dist[nxt_v] = d
                if cost == 0:
                    que.appendleft(nxt_v)
                else:
                    que.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

01-BFS (Graph/ShortestPath/bfs01.py)

概要

使い方

参考

Code

01-BFS
(Graph/ShortestPath/bfs01.py)