Bellman-Ford’s algorithm (벨만-포드)

# 정의

벨만-포드 알고리즘은 음의 가중치를 가지는 간선이 있는 그래프에서 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘과 다르게, 그래프 내의 모든 정점을 대상으로 최단 경로를 갱신하므로 음의 가중치를 가지는 간선이 있어도 사용할 수 있습니다. 그러나 음의 사이클이 존재하는 경우에는 최단 경로를 구할 수 없습니다.

벨만포드를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야합니다. 다른 글에서 설명을 이미 했기 때문에 링크만 올려두겠습니다.

https://whitem4rk.tistory.com/18

BFS (Breadth First Search )

 

---

# Code

알고리즘의 동작 방식

1. 그래프의 모든 정점에 대해 초기 거리 값을 무한대로 설정합니다.
2. 출발점의 거리 값을 0으로 설정합니다.
3. 그래프 내의 모든 간선을 순서대로 탐색하며, 각 간선에 대해 다음을 수행합니다.
   • 간선의 시작 정점의 거리 값에 간선의 가중치를 더한 값이 끝 정점의 거리 값보다 작은 경우, 끝 정점의 거리 값을 갱신합니다.
4. 모든 간선에 대한 탐색을 V-1번 반복합니다. (V는 정점의 개수입니다.)
5. 음의 사이클이 존재하는지 확인합니다. 이를 위해 다음을 수행합니다.
   • 모든 간선에 대해 다시 한번 탐색하며, 간선의 시작 정점의 거리 값에 간선의 가중치를 더한 값이 끝 정점의 거리 값보다 작은 경우, 음의 사이클이 존재한다는 의미입니다.

가장 기본적인 벨만포드 알고리즘 파이썬 코드입니다.

INF = float('inf')

def bellman_ford(graph, start):
    # 모든 정점까지의 최단 거리를 저장하는 배열
    dist = [INF] * len(graph)
    dist[start] = 0

    # 최단 경로를 저장하는 배열
    path = [[] for _ in range(len(graph))]
    path[start].append(start)

    # 모든 정점을 순회하는 V-1번의 라운드 수행
    for i in range(len(graph)-1):
        # 모든 에지를 순회하며 거리 갱신
        for u in range(len(graph)):
            for v, weight in graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    path[v] = path[u] + [v] # 경로를 추가로 저장

    # 음수 사이클 체크
    for u in range(len(graph)):
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                raise ValueError("Negative cycle detected")

    # 최단 경로를 반환
    return dist, path

 

---

# 수행시간

벨만-포드 알고리즘은 에지를 순회하는 횟수가 정점의 개수와 에지의 개수의 곱인 O(V * E)입니다.

 

---

# 벨만포드의 실제쓰임

1. 은행 간의 송금이나 환전 시 최적 경로를 찾는 데 사용
2. 네트워크 분야에서는 데이터 패킷을 전송할 때 최단 경로를 찾는 데 사용
3. 어떤 문장에서 주어진 단어들 간의 의존성 파싱(dependency parsing)을 할 때, 각 단어들 간의 관계를 그래프로 모델링하고, 벨만-포드 알고리즘을 이용해 최단 경로를 찾는 방식을 사용

 

---

# 벨만포드 vs 다익스트라

두 알고리즘 모두 한 정점에서 모든 정점까지의 최단경로를 찾습니다. 각각의 알고리즘이 어떤 상황에 더 적합할지 정할 수 있는 기준점이 있습니다.

1. 음의 가중치를 가지는 그래프의 사용여부
   벨만포드는 음의 가중치를 가지는 그래프에서도 최단경로를 찾을 수 있지만 다익스트라는 양의 가중치를 가지는 그래프에서만 사용됩니다. 
2. 수행시간
   벨만포드는 O(|V| * |E|) 의 시간복잡도를 가지지만 다익스트라의 경우 O(|E| * |V| log |V|)의 시간복잡도를 가집니다.

한 줄로 표현하자면 벨만포드는 범용성을, 다익스트라는 효율성을 가졌습니다.

 

 

 

 

---

# Reference

ChatGPT