벨만-포드 알고리즘은 그래프에서 최단 경로를 찾기 위해 사용되는 알고리즘 중 하나입니다. 이 알고리즘은 음의 가중치를 가진 그래프에서도 동작하며, 가중치의 합이 음수 싸이클이 없을 경우에만 최단 경로를 구할 수 있습니다.

알고리즘 동작 원리

벨만-포드 알고리즘은 시작 정점에서부터 모든 다른 정점까지의 최단 경로를 차례대로 구하는 방식으로 동작합니다. 각 정점까지의 최단 경로는 이전 정점까지의 최단 경로와 현재 정점까지의 가중치를 더한 값으로 갱신됩니다. 이 과정을 모든 정점에 대해 반복하면, 마지막 반복에서 최단 경로가 최종적으로 결정됩니다.

구현 예제

다음은 파이썬으로 벨만-포드 알고리즘을 구현한 예제입니다.

def bellman_ford(graph, start):
    # 정점들의 거리를 초기화
    distance = {node: float('inf') for node in graph}
    distance[start] = 0

    # 모든 간선에 대해 반복적으로 최단 거리를 업데이트
    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distance[node] != float('inf') and distance[node] + weight < distance[neighbor]:
                    distance[neighbor] = distance[node] + weight

    # 음의 사이클 확인
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distance[node] != float('inf') and distance[node] + weight < distance[neighbor]:
                raise Exception("음의 사이클이 존재합니다.")

    return distance

위의 예제에서 graph는 그래프를 나타내는 딕셔너리입니다. 각 정점을 키로 가지고, 인접한 정점과 그 가중치를 값으로 가지고 있습니다. start는 시작 정점을 나타냅니다. bellman_ford 함수는 시작 정점부터 모든 정점까지의 최단 거리를 반환합니다.

시간 복잡도

벨만-포드 알고리즘의 시간 복잡도는 O(V*E)입니다. V는 정점의 개수이고, E는 간선의 개수입니다. 따라서 그래프의 크기가 매우 큰 경우에는 성능 문제가 발생할 수 있습니다.

결론

벨만-포드 알고리즘은 음의 가중치를 가진 그래프에서도 최단 경로를 찾을 수 있는 알고리즘입니다. 하지만 시간 복잡도가 크기 때문에 그래프의 크기가 큰 경우에는 성능 문제가 발생할 수 있으므로 주의해야 합니다.