> For the complete documentation index, see [llms.txt](https://kde6260.gitbook.io/dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kde6260.gitbook.io/dev/bellman-ford.md).

# 벨만-포드(Bellman-Ford) 알고리즘

최초작성일 \[2020.01.20]

### 벨만-포드 알고리즘

다익스트라 알고리즘은 서로 다른 두 정점 사이의 간선의 가중치가 0보다 크거나 같을 경우 최단 경로를 찾는 데 적절한 알고리즘이라면 벨만-포드(Bellman-Ford)알고리즘은 간선의 가중치가 음수일 때 최단 경로를 찾기 적절한 알고리즘이다.

벨만-포드 알고리즘은 출발 정점의 `dist`를 0으로 설정한 뒤, 그래프 내 모든 간선을 대상으로 relaxation을 수행한다. 이 relaxation은 출발 정점을 제외한 나머지 `|V| - 1` 번 수행하므로 시간복잡도는 `O(|V| * |E|)` 이다.

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-Lz2CU3FoFLYKGr_RvZu%2F-Lz2LzWR80nk3NmZ5Ul6%2Fbellmanford.jpg?alt=media\&token=aeccdf1d-f02f-42f2-a031-ddc6d9b8d6ad)

1. 출발 정점 A의 `dist`를 0으로, 나머지 정점의 `dist`는 무한대로 설정한다.
2. 모든 간선(총 9개)를 대상으로 relaxation을 수행한다. relaxation을 수행하는 간선의 순서는 상관없다. 
3. 2번을 `|V| - 1`번 수행한다.

위 과정을 거치면 그림의 왼쪽에서 오른쪽으로 각 정점의 dist가 갱신되며, 각 dist는 출발 정점 A에서 각 정점으로 향하는 최단 거리를 나타낸다.

벨만-포드 알고리즘을 코드로 구현하면 아래와 같다.

```python
def relax(v1, v2):
  if dist[v2] > dist[v1] + weight(v1, v2):
    dist[v2] = dist[v1] + weight(v1, v2)
    prev[v2] = v1


def Bellman-Ford(G, start):
  for u in V:
    dist[u] = infinity
    prev[u] = nil
    
  dist[start] = 0
  
  for _ in range(|V| - 1):  # O(|V|)
    for (v1, v2) in G:      # O(|E|)
      relax(v1, v2)
```

### Negative Cycle

negative cycle이란 음수 가중치를 가지는 그래프의 사이클에 의해 두 정점의 거리가 음의 무한대로 계산되는 것을 말한다.

![](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-Lz2CU3FoFLYKGr_RvZu%2F-Lz2RjEdCz_USATpwkN1%2Fnegative_cycle.jpg?alt=media\&token=2b948fc5-895b-4f15-a49c-9cd6ceb40b65)

위 그림과 같이 그래프에서 negative cycle을 이루면 벨만-포드 알고리즘을 적용할 수 없다. 

**증**

어떤 그래프에 negative cycle이 있지만 벨만-포드 알고리즘으로 최단거리를 구할 수 있다고 가정해보자. `|V| - 1` 번의 relaxation을 거치고나면 출발정점에서 각 정점으로의 최단거리가 구해지므로, `|V|`번째 relaxation을 했을 때 모든 정점의 `dist`는 갱신될 일이 없어야 한다. 

`|V|`번째의 relaxation에서 정점 `A`, `B`, `C`의 `dist`가 갱신될 일이 없으려면 아래의 조건이 모두 참이어야 한다.

```python
dist[A] <= dist[C] + weight(C, A)
dist[B] <= dist[A] + weight(A, B)
dist[C] <= dist[B] + weight(B, C)
```

위 조건들이 참이 되려면 `weight(C, A)`, `weight(A, B)`, `weight(B, C)`는 모두 0보다 같거나 큰, 음이 아닌 수여야 한다. 하지만 negative cycle을 이루는 `A`, `B`, `C` 사이의 간선에는 음의 가중치가 존재하므로 가정과 모순을 이룬다. 따라서 벨만-포드 알고리즘은 negative cycle을 이루는 그래프에서 최단 거리를 구할 수 없음을 증명한다.

**‌**

### **N**egative Cycle 찾는 방법

1. `|V|`번째 relaxation에 dist가 갱신되는 모든 정점을 찾아서 큐에 저장한다. 이 정점들이 negative cycle에 있는 정점들이다.(negative cycle에 포함되지 않는 정점은 `|V|`번째 relaxtion에서 dist가 갱신될 일이 없다.)
2. 큐를 이용하여 BFS를 수행한다.
3. BFS를 수행하면서 큐에 있는 정점들과 인접한 다른 정점들을 탐색한다.

negative cycle을 찾는 방법은 무한차익거래(infinite arbitrage)를 찾아내는 알고리즘에도 활용할 수 있다.

출처

* [코세라 알고리즘 강의](https://www.coursera.org/learn/algorithms-on-graphs?specialization=data-structures-algorithms)
* [ratsgo.github.io - 벨만포드 알고리즘](https://ratsgo.github.io/data%20structure\&algorithm/2017/11/27/bellmanford/)