[MIT] 파이썬을 이용한 알고리즘의 이해 - 최단 경로 3 : 벨만 포드

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

✔ 복습

 정점 u에서 v까지의 최단 경로의 가중치를 δ(u, v)로 둡니다. 정점 u에서 정점 v가 도달 불가능하면 δ(u, v)의 값은 무한대(∞)입니다. 정점 u와 v사이에 음의 순환이 있으면 최단 경로는 정의되지 않습니다.

 

 

 

✔ 일반적 최단 경로 알고리즘

⁉️ 문제점

• 양의 가중치를 가지고 있는 간선도 지수 시간 복잡도를 가집니다.
  → 다익스트라 알고리즘을 이용하여 해결 가능합니다.

• 음의 가중치를 가진 순환이 시작점으로부터 도달이 가능하다면 알고리즘이 아예 끝나지 않을 수도 있습니다.

 

 

 

✔ 벨만-포드 알고리즘

: 음의 순환이 없다면 알고리즘의 마지막엔 d[v] = δ(s, v)입니다. 다익스트라 알고리즘은 거의 선형 복잡도를 가지지만 벨만 포드 알고리즘은 O(V^3)의 복잡도를 가질 수 있습니다.(전체 시간 복잡도는 O(VE)이고 E는 단순 그래프에서 O(V^2)입니다.)

 

⁉️ 정리

: 그래프 G = (V,E)가 음의 순환을 가지고 있지 않으면 벨만 포드 알고리즘의 종료 후 모든 그래프의 정점 v ∈ V에 대해 d[v] = δ(s, v)입니다. 

 v ∈ V를 그래프 내 임의의 정점이라고 하면 정점 v0 = s에서 vk = v 까지의 경로 p = < v0 , v1 ,..., vk >를 최소 개수의 간선을 가진 최단 경로입니다. 음의 순환이 없으면 경로 p는 단순 경로입니다. p가 단순 경로이면 k ≤|V|−1입니다.

 알고리즘의 시작에서 d[v0] = 0 = δ(s, v0)이고 음의 순환이 없으므로 이 값은 변하지 않습니다. 모든 간선 E에 대해 첫 번째 완화 과정을 거치면, d[v1]의 값은 다음과 같이 갱신됩니다. → d[v1] = δ(s, v1).

 첫 번째 계산을 통해 간선 (v0 , v1)이 완화되고 이 최단 경로보다 더 짧은 경로를 찾을 수 없기 때문입니다. 간선 E에 대해 두 번째 완화 과정을 거치면, d[v2] = δ(s, v2)입니다.(두 번째 완화 과정에서 간선 (v1, v2)가 완화되기 때문입니다.)

 모든 간선 E에 대해 i번 완화 가정을 가지면, d[vi] = δ(s, vi)로 값이 갱신됩니다. k ≤ |V|−1 번째 완화 과정을 E의 각 간선에 대해 실행하면, d[vk] = d[v] = δ(s, v)의 결과를 얻을 수 있습니다.

 

⁉️ 따름 정리

: d[v]의 값이 v-1번의 계산 이후에도 수렴하지 못한다면 정점 s로부터 음의 순환에 도달할 수 있다는 정리입니다. |V|−1번 완화 과정을 거친 후에도 완화될 수 있는 간선을 찾을 수 있다면 현 최단 경로가 단순 경로가 아니고 같은 정점을 중복 방문한다는 것을 의미합니다. 순환을 포함한 이 경로가 단순 경로보다 가중치가 작으므로 이 순환은 음의 가중치를 가집니다.

 

 

⁉️ 최장 단순 경로와 최단 단순 경로

 양의 가중치를 가지는 그래프에서 최장 단순 경로를 찾는 문제는 NP-hard 문제입니다. 즉, 알려진 다항시간 알고리즘이 존재하지 않습니다. 각 간선의 가중치를 음수화하고 벨만-포드 알고리즘을 이용해 최단 경로를 계산한다고 생각해보면 벨만 포드 알고리즘은 음의 순환이 시작점에서 도달 가능하면 바로 종료해버리기 때문에 실질적으로 기존 그래프의 최장 경로를 계산하지 못합니다. 유사하게 음의 순환을 가지고 있는 그래프가 있고, 정점 s에서 v까지의 최장 단순 경로를 계산하고 싶다면 벨만-포드 알고리즘을 사용할 수 없습니다. 최단 단순 경로를 구하는 문제 역시 NP-hard입니다.