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