Dijkstra
(byslib/graph/dijkstra.py)

• View this file on GitHub
• Last update: 2022-04-18 22:29:22+09:00

Verified with

• tests/graph/dijkstra.test.py

Code

# @title Dijkstra
import heapq
from typing import Iterable, List, Tuple, Union

from ..core.const import IINF
from .graph import LilMatrix


def dijkstra(
    graph: LilMatrix, source: Union[int, Iterable[int]]
) -> Tuple[List[int], List[int]]:
    """Dijkstra

    Parameters
    ----------
    graph
        Weighted Graph
    source
        (list of) source

    Returns
    -------
        (cost, prev)

    Notes
    -----
    Time complexity

    O(V + Elog(V))

    References
    ----------
    ..[1] 🐜 p.96

    """
    n = len(graph)
    cost = [IINF] * n
    prev = [-1] * n
    que: List[Tuple[int, int]] = []

    if isinstance(source, int):
        que = [(0, source)]
        cost[source] = 0
    else:
        que = [(0, si) for si in source]
        for si in source:
            cost[si] = 0
    heapq.heapify(que)

    while que:
        top_cost, top = heapq.heappop(que)
        if cost[top] < top_cost:
            continue
        for dest, weight in graph[top]:
            nxt_cost = cost[top] + weight
            if nxt_cost < cost[dest]:
                cost[dest] = nxt_cost
                prev[dest] = top
                heapq.heappush(que, (nxt_cost, dest))

    return cost, prev

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/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], 'release': True}).decode()
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/python.py", line 80, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page