zerohertzLib.algorithm.graph ¶

def bellman_ford(graph: list[list[tuple[int, int]]], start: int) -> list[int] | None:
    """Graph에서 시작 node로부터 모든 다른 node까지의 최단 경로 거리 계산

    Note:
        Time Complexity: $O(VE)$

        - $V$: Node의 수
        - $E$: 간선의 수

    Args:
        graph: Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보
        start: 최단 경로 거리가 계신될 시작 node

    Returns:
        `start` 에서 graph 내 모든 다른 node 까지의 최단 경로 거리 (음의 cycle을 가질 시 None return)

    Examples:
        >>> graph = [[(1, 4), (2, 2), (3, 7)], [(0, 1), (2, 5)], [(0, 2), (3, 4)], [(1, 3)]]
        >>> zz.algorithm.bellman_ford(graph, 0)
        [0, 4, 2, 6]
        >>> zz.algorithm.bellman_ford(graph, 1)
        [1, 0, 3, 7]
        >>> zz.algorithm.bellman_ford(graph, 2)
        [2, 6, 0, 4]
        >>> zz.algorithm.bellman_ford(graph, 3)
        [4, 3, 6, 0]
        >>> zz.algorithm.bellman_ford([[(1, -1)], [(0, -1)]], 0) is None
        True
    """
    n = len(graph)
    distance = [sys.maxsize for _ in range(n)]
    distance[start] = 0
    for cnt in range(n):
        for node in range(n):
            for node_, dist_ in graph[node]:
                if (
                    distance[node] != sys.maxsize
                    and distance[node_] > distance[node] + dist_
                ):
                    distance[node_] = distance[node] + dist_
                    if cnt == n - 1:
                        return None
    return distance

def bfs(maps: list[list[int]], start: int) -> list[int]:
    """BFS를 수행하기 위한 function

    Args:
        maps: 입력 graph
        start: Graph의 시작 지점

    Returns:
        방문 순서

    Examples:
        >>> zz.algorithm.bfs([[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]], 1)
        [1, 2, 3, 4]
    """
    visit = [False for _ in range(len(maps))]
    results = []
    queue = deque()
    queue.append(start)
    visit[start] = True
    while queue:
        tmp = queue.popleft()
        results.append(tmp)
        for i in maps[tmp]:
            if not visit[i]:
                visit[i] = True
                queue.append(i)
    return results

def dfs(maps: list[list[int]], start: int) -> list[int]:
    """DFS를 수행하기 위한 function

    Args:
        maps: 입력 graph
        start: Graph의 시작 지점

    Returns:
        방문 순서

    Examples:
        >>> zz.algorithm.dfs([[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]], 1)
        [1, 2, 4, 3]
    """
    visit = [False for _ in range(len(maps))]
    results = []

    def _dfs(start):
        visit[start] = True
        results.append(start)
        for i in maps[start]:
            if not visit[i]:
                _dfs(i)

    _dfs(start)
    return results

def dijkstra(graph: list[list[tuple[int, int]]], start: int) -> list[int]:
    r"""Graph에서 시작 node로부터 모든 다른 node까지의 최단 경로 거리 계산

    Note:
        Time Complexity: $O((V+E)\log{V})$

        - $V$: Node의 수
        - $E$: 간선의 수

    Args:
        graph: Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보
        start: 최단 경로 거리가 계신될 시작 node

    Returns:
        `start` 에서 graph 내 모든 다른 node 까지의 최단 경로 거리 (음의 가중치에서는 정확하지 않음)

    Examples:
        >>> graph = [[(1, 4), (2, 2), (3, 7)], [(0, 1), (2, 5)], [(0, 2), (3, 4)], [(1, 3)]]
        >>> zz.algorithm.dijkstra(graph, 0)
        [0, 4, 2, 6]
        >>> zz.algorithm.dijkstra(graph, 1)
        [1, 0, 3, 7]
        >>> zz.algorithm.dijkstra(graph, 2)
        [2, 6, 0, 4]
        >>> zz.algorithm.dijkstra(graph, 3)
        [4, 3, 6, 0]
    """
    distance = [sys.maxsize for _ in range(len(graph))]
    distance[start] = 0
    queue = [(0, start)]
    while queue:
        dist, node = heapq.heappop(queue)
        if distance[node] < dist:
            continue
        for node_, dist_ in graph[node]:
            if distance[node_] > dist + dist_:
                distance[node_] = dist + dist_
                heapq.heappush(queue, (dist + dist_, node_))
    return distance

def floyd_warshall(graph: list[list[tuple[int, int]]]) -> list[list[int]] | None:
    """Graph에서 모든 node 쌍 간의 최단 경로 거리 계산

    Note:
        Time Complexity: $O(V^3)$

        - $V$: Node의 수

    Args:
        graph: Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보

    Returns:
        모든 node 쌍에 대한 최단 경로 거리 (음의 cycle을 가질 시 None return)

    Examples:
        >>> graph = [[(1, 4), (2, 2), (3, 7)], [(0, 1), (2, 5)], [(0, 2), (3, 4)], [(1, 3)]]
        >>> zz.algorithm.floyd_warshall(graph)
        [[0, 4, 2, 6], [1, 0, 3, 7], [2, 6, 0, 4], [4, 3, 6, 0]]
    """
    n = len(graph)
    distance = [[sys.maxsize for _ in range(n)] for _ in range(n)]
    for i in range(n):
        distance[i][i] = 0
        for j, dist in graph[i]:
            distance[i][j] = dist
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if (
                    distance[i][j] > distance[i][k] + distance[k][j]
                    and distance[i][k] != sys.maxsize
                    and distance[k][j] != sys.maxsize
                ):
                    distance[i][j] = distance[i][k] + distance[k][j]
    for i in range(n):
        if distance[i][i] < 0:
            return None
    return distance