Warshall Floyd
(byslib/graph/warshall_floyd.py)

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

Code

# @title Warshall Floyd
from typing import List

from ..core.const import IINF
from .edge import Edge


def warshall_floyd(elist: List[Edge], n: int) -> List[List[int]]:
    """warshall floyd

    Parameters
    ----------
    elist
        List of Edge
    n
        Vertex Size

    Returns
    -------
    Cost matrix

    Notes
    -----
    Time complexity

    O(N^3)

    References
    ----------
    ..[1] 🐜 p.98
    """
    cost = [[IINF] * n for _ in range(n)]
    for e in elist:
        cost[e.src][e.dest] = e.weight
    for i in range(n):
        cost[i][i] == 0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if cost[i][k] == IINF or cost[k][j] == IINF:
                    continue
                tmp_cost = cost[i][k] + cost[k][j]
                if cost[i][j] > tmp_cost:
                    cost[i][j] = tmp_cost

    return cost

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