[그래프] 벨만-포드 / Bellman–Ford algorithm

https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

Bellman–Ford algorithm 벨만-포드 알고리즘

벨만-포드(Bellman-Ford) 알고리즘은 그래프에서 음의 가중치를 허용하면서 단일 출발점 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘과는 달리 음의 사이클을 탐지할 수 있는 특성 때문에 특정 문제들(예: 네트워크에서 음의 가중치가 있는 경로 등)을 해결하는 데 유용합니다.

벨만-포드 알고리즘의 특징

• 시간 복잡도: O(V * E), 여기서 V는 정점의 개수, E는 간선의 개수입니다. 따라서, 다익스트라보다 느리지만 음의 가중치를 포함할 수 있다는 장점이 있습니다.
• 음의 가중치: 음의 가중치를 허용합니다. 다익스트라와 달리, 음의 사이클이 있을 때도 탐지할 수 있습니다.
• 음의 사이클 탐지: 벨만-포드는 그래프에 음의 사이클이 존재하는지 확인할 수 있는 능력이 있습니다. 음의 사이클이 존재하면, 어떤 지점에서 출발해 다시 돌아올 때 더 짧아질 수 있습니다.

벨만-포드 알고리즘 동작 원리

1. 초기화: 모든 정점에 대해 출발 정점에서의 거리를 무한대로 설정합니다. 출발 정점의 거리는 0으로 설정합니다.
2. 간선 완화: 그래프의 모든 간선을 반복적으로 완화합니다. 완화(relaxation)란, 특정 간선을 통해 이동할 때 더 짧은 경로를 찾으면 해당 거리를 업데이트하는 것을 말합니다. 이 작업을 V-1번 반복합니다. (V는 정점의 수)
3. 음의 사이클 탐지: V-1번 반복한 후, 추가적으로 한 번 더 모든 간선을 확인해서 거리가 줄어드는 간선이 있다면, 음의 사이클이 존재하는 것입니다.

벨만-포드 알고리즘 단계

1. 그래프와 거리 배열 초기화:
   • 그래프는 Edge 구조체 리스트로 표현됩니다.
   • 거리 배열 dist는 모든 정점의 거리를 무한대로 설정하고, 출발점의 거리는 0으로 설정합니다.
2. 반복적 완화 과정:
   • 각 간선을 확인하고, from에서 to로 가는 경로가 더 짧다면 거리를 갱신합니다.
3. 음의 사이클 확인:
   • 모든 간선을 한 번 더 확인하여, 만약 더 짧아질 수 있는 경로가 존재한다면 음의 사이클이 있다고 결론짓습니다.

 

예시코드) BOJ swift 1865 웜홀

import Foundation

struct Edge {
    var s: Int, e: Int, t: Int
}

let tc = Int(readLine()!)!

for _ in 0..<tc {
    let nmw = readLine()!.split(separator: " ").map{Int(String($0))!}
    let (n, m, w) = (nmw[0], nmw[1], nmw[2])
    var edges: [Edge] = []
    
    for _ in 0..<m {
        let set = readLine()!.split(separator: " ").map{Int(String($0))!}
        let edge = Edge(s: set[0], e: set[1], t: set[2])
        let reverseEdge = Edge(s: set[1], e: set[0], t: set[2])
        edges.append(edge)
        edges.append(reverseEdge)
    }
    
    for _ in 0..<w {
        let set = readLine()!.split(separator: " ").map{Int(String($0))!}
        let edge = Edge(s: set[0], e: set[1], t: -set[2])
        edges.append(edge)
    }
    
    var dist = Array(repeating: 987654321, count: n + 1)
    dist[1] = 0
    
    for _ in 0..<n-1 {
        for edge in edges {
            if dist[edge.e] > dist[edge.s] + edge.t {
                dist[edge.e] = dist[edge.s] + edge.t
            }
        }
    }
    
    var hasNegativeCycle = false
    for edge in edges {
        if dist[edge.e] > dist[edge.s] + edge.t {
            hasNegativeCycle = true
            break
        }
    }
    
    if hasNegativeCycle { print("YES") }
    else { print("NO") }
}