음수를 가진 최적경로 탐색 - 벨만포드(Bellman ford) 알고리즘 정리

https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

 

벨판 포드 알고리즘은 특정 유형의 문제에서 Dijkstra알고리즘으로 해결하지 못하는 단점을 보완하기 위해 사용되는 알고리즘 입니다.

 

Dijkstra 알고리즘과 유사하게 벨만 포드 알고리즘도 가중치가 있는 경로에서 최단 거리를 구하는 문제이지만 만약 음수의 가충치가 있는 경로에서는 정확도가 떨어지는 문제가 있어 적용할 수 없는 단점이 있습니다.

 

여기서 Dynamic Programming을 활용한 벤만포드 알고리즘을 적용합니다.

 

아이디어는 이렇습니다.

 

N개수의 노드가 있다고 할 때, 모든 노드에서 경로를 N - 1 만큼 반복적으로 각 노드 간 경로 비용을 비교분석하여 계속 짧게 나온 값을 선택하는 방법입니다. 그렇게 N - 1 만큼 반복을 완료하여 나온 값들 중 가장 낮은 경로를 고르면 해당 경로가 답이 되는 방식입니다.

 

벨만 포드의 단점은 최악의 상황인 경우, 모든 노드의 경로가 모든 노드로 연결되었을 때, N * (N * ( N - 1) / 2) O(n^3) 만큼 걸린다는 단점이 있습니다. 또한 벨만 포드는 만약 루프가 있는 노드로 구성되어 있으면 루프를 돌 때마다 지속적으로 값이 변하기 때문에 루프의 합이 음수로 설정 될 경우 정확한 값을 추정하기 어렵다는 점이 있습니다.

 

따라서 밸만 포드는 방향성 그래프에 적용되고 그래프에서 내부적으로 순회하는 구간이 없어야 하며, 빠른 연산이 중요하지 않을 때 사용되는 알고리즘 이라고 보면 될 것 같습니다.

 

출처: https://www.youtube.com/watch?v=FtN3BYH2Zes

 

 

---

 

코드 예시

from typing import Dict

class Node:
    def __init__(self, name):
        self.name = name
        self.adjacent : Dict[str, 'Node'] = {}
        self.edge_cost : Dict[str, int] = {}
        self.weight = float('inf')
    
    def swap(self, calculated_weight):
        if self.weight > calculated_weight:
            self.weight = calculated_weight

    def get_weight(self):
        return self.weight

    def add_adjacent_node(self, name : str, node : 'Node', cost : int):
        self.adjacent[name] = node
        self.edge_cost[name] = cost

    def get_adjacent_nodes(self):
        return self.adjacent
    
    def get_edge_cost(self, node_name: str):
        return self.edge_cost[node_name]
    
    def __repr__(self):
        # Makes printing nodes easier to read
        return f"Node({self.name}, weight={self.weight})"

def bellman_ford(graph : Dict[str, Dict[str, int]], source: str, destination: str):
    #노드화
    nodes : Dict[str, Node] = {name : Node(name) for name in graph.keys()}
    nodes[source].weight = 0 #출발지 초기화

    #간선 리스트 구성
    edges = []

    #간선 연결
    for current_node_name, neighbors in graph.items():
        neighbors : Dict[str, int]
        for neighbor_name, path_cost in neighbors.items():
            nodes[current_node_name].add_adjacent_node(neighbor_name, nodes[neighbor_name], path_cost)
            edges.append((current_node_name, neighbor_name))

    #N-1 만큼 간선 리스트 반복 수행, 각 노드 별 가중치 업데이트 (Relax edges)
    for _ in range(len(nodes) - 1):
        for edge in edges:
            u : Node = nodes[edge[0]] #from
            v : Node = nodes[edge[1]] #to
            cost = nodes[u.name].get_edge_cost(v.name)
            #if (u's weight + cost) -> v is smaller, swap v's cost
            if u.get_weight() + cost < v.get_weight():
                v.swap(u.get_weight() + cost)

    #음수 사이클 판단 - 존재 시 끝내기
    for edge in edges:
        u : Node = nodes[edge[0]] #from
        v : Node = nodes[edge[1]] #to
        cost = u.get_edge_cost(v.name)
        if u.weight != float('inf') and u.weight + cost < v.weight:
            print(f"Graph contains a negative weight cycle involving edge ({u.name}->{v.name})")
            return None

    return nodes[destination].get_weight()

if __name__ == "__main__":

    # --- Example Graph (with a negative edge, but no negative cycle) ---
    #
    #      4       3
    #   S ----> A ----> C
    #   |     / |       |
    #  2|   1/  |-1     |-2
    #   |  /    |       |
    #   V V     V       V
    #   B ----> D <---- E
    #      -2
    #
    vertices = {'S', 'A', 'B', 'C', 'D', 'E'}
    
    # Format: (source_node, destination_node, weight)
    graph = {
        'S': {'A': 4, 'B': 2},
        'A': {'C': 3, 'D': -1},
        'B': {'A': 1, 'D': -2},
        'C': {'E': 2},
        'E': {'D': -2},
        'D': {}
    }
    source_node = 'S'

    print(bellman_ford(graph, source_node, 'E')) #8을 반환


    # --- Optional: Negative Cycle Graph as a Dictionary ---
    graph_cycle = {
        'A': {'B': 1},
        'B': {'C': -5},
        'C': {'D': 1},
        'D': {'B': 2}
    }
    source_node_cycle = 'A'

    print(bellman_ford(graph_cycle, source_node_cycle, 'D')) #음수 사이클은 Null 반환