BFS
(Graph/ShortestPath/bfs.py)

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

概要

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

使い方

bfs(graph: Sequence[Sequence[int]], start: int) -> List[int]
各辺の長さが $1$ の有向グラフ graph 上での、start を始点とした単一始点最短距離の配列を返す。計算量 $O(V + E)$

Verified with

• TestCase/AOJ/ALDS1_11_C.test.py

Code

# from collections import deque
from standard_library.collections import deque


def bfs(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 in graph[v]:
            if dist[nxt_v] == INF:
                dist[nxt_v] = dist[v] + 1
                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

Back to top page