Source code for titan_pylib.graph.dijkstra

 1from typing import Union
 2from heapq import heappush, heappop
 3
 4

[docs]
 5def dijkstra(
 6    G: list[list[tuple[int, int]]], s: int, INF: Union[int, float] = float("inf")
 7) -> list[Union[int, float]]:
 8    """ダイクストラです。
 9
10    Args:
11        G (list[list[tuple[int, int]]]): 隣接リストです。
12        s (int): 始点です。
13        INF (Union[int, float], optional): 無限大です。
14
15    Returns:
16        list[Union[int, float]]: 各頂点について、 ``s`` からの最短距離を返します。
17    """
18    dist = [INF] * len(G)
19    dist[s] = 0
20    hq: list[tuple[int, int]] = [(0, s)]
21    while hq:
22        d, v = heappop(hq)
23        if dist[v] < d:
24            continue
25        for x, c in G[v]:
26            if dist[x] > d + c:
27                dist[x] = d + c
28                heappush(hq, (d + c, x))
29    return dist