안녕하세요! 이번 강좌에서는 스위프트를 사용하여 벨만-포드 알고리즘에 대해 다뤄보도록 하겠습니다. 벨만-포드 알고리즘은 그래프에서 단일 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘으로, 음의 가중치를 가진 간선이 있는 그래프에서도 사용할 수 있다는 장점이 있습니다. 이 강좌에서는 벨만-포드 알고리즘의 개념을 설명하고, 구체적인 알고리즘의 구현 과정을 살펴보겠습니다.
1. 벨만-포드 알고리즘 개요
벨만-포드 알고리즘은 1958년 리처드 벨만과 라인하르트 포드에 의해 개발되었습니다. 이 알고리즘은 다음과 같은 방식으로 작동합니다:
- 그래프의 모든 간선에 대해 초기화된 거리 배열을 업데이트합니다.
- 최대 정점의 수 – 1 만큼 간선을 Relaxation하여 거리 정보를 최적화합니다.
- 음의 사이클 검사를 추가하여, 음수 순환이 존재하는지 확인합니다.
1.1. 알고리즘 절차
- 최초 거리를 무한대로 설정하며, 시작점의 거리는 0으로 초기화합니다.
- 모든 간선에 대해 최대 V-1번 반복하여 Relaxation을 수행합니다.
- 마지막으로 모든 간선에 대해 음의 사이클을 검사합니다.
2. 문제를 정의해보기
이제 벨만-포드 알고리즘을 사용할 수 있는 문제를 정의해보겠습니다.
문제: 최단 경로 찾기
그래프의 정점 수
V, 간선 수E이 주어지고, 간선의 정보가 주어집니다. 시작 정점에서 모든 다른 정점까지의 최단 경로를 구하시오. 단, 그래프가 음의 사이클을 포함할 때는 “Negative Cycle”을 출력하시오.
입력 형식
V (정점 수) E (간선 수) 간선 정보 (시작 정점, 끝 정점, 가중치)
출력 형식
각 정점까지의 최단 거리 또는 "Negative Cycle"
3. 벨만-포드 알고리즘의 구현
문제를 정의했으니, 이제 스위프트를 사용해 알고리즘을 구현해보겠습니다.
import Foundation
struct Edge {
let from: Int
let to: Int
let weight: Int
}
func bellmanFord(vertices: Int, edges: [Edge], start: Int) -> [Int] {
var distances = Array(repeating: Int.max, count: vertices)
distances[start] = 0
// Relaxation 단계
for _ in 0..3.1. 사용 예시
이제 위의 알고리즘을 테스트해보겠습니다. 다수의 간선과 정점을 가진 그래프를 예로 들어보겠습니다.
let edges = [
Edge(from: 0, to: 1, weight: 4),
Edge(from: 0, to: 2, weight: 1),
Edge(from: 2, to: 1, weight: 2),
Edge(from: 1, to: 3, weight: 1),
Edge(from: 2, to: 3, weight: 5)
]
let result = bellmanFord(vertices: 4, edges: edges, start: 0)
if !result.isEmpty {
for (index, distance) in result.enumerated() {
print("정점 \(index): \(distance)")
}
}
4. 알고리즘 시간 복잡도
벨만-포드 알고리즘은 V개의 정점과 E개의 간선이 있을 때, 최악의 경우 O(VE)의 시간 복잡도를 가지고 있습니다. 이로 인해 비교적 작은 그래프에서 효율적으로 사용할 수 있지만, 간선이 많아지는 경우에는 시간이 많이 걸릴 수 있습니다.
5. 마무리
이번 강좌에서는 벨만-포드 알고리즘의 기본 개념과 그것을 이용한 문제의 정의, 알고리즘 구현 그리고 사용 예에 대해 알아보았습니다. 벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서도 최단 경로를 찾을 수 있는 유용한 알고리즘임을 알 수 있었습니다. 이 알고리즘을 활용해 다양한 문제를 풀어보시기 바랍니다.
다음 시간에는 다익스트라 알고리즘에 대해 다뤄보겠습니다. 감사합니다!