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

벨만-포드 알고리즘은 그래프에서 **최단 경로(Shortest Path)**를 구하기 위한 알고리즘으로, 특히 음수 가중치 간선을 포함한 그래프에서도 작동합니다.

이 알고리즘은 단순하면서도 강력하며, 음수 사이클(negative weight cycle)을 감지할 수도 있습니다.

---

알고리즘의 특징

1. 음수 가중치 허용:
   • 다익스트라 알고리즘은 음수 가중치 간선이 있는 그래프에서는 사용할 수 없지만, 벨만-포드 알고리즘은 음수 가중치를 포함한 그래프에서도 작동합니다.
2. 음수 사이클 탐지:
   • 음수 사이클이 존재하는 경우, 무한히 작은 경로를 만들 수 있기 때문에 최단 경로를 계산할 수 없습니다.
   • 벨만-포드 알고리즘은 음수 사이클의 존재 여부를 확인할 수 있습니다.
3. 시간 복잡도:
   • O(V×E)O(V \times E)O(V×E), 여기서 VVV는 정점의 개수, EEE는 간선의 개수.
   • 모든 간선을 최대 V−1V - 1V−1번 반복하며 처리하기 때문.
4. 공간 복잡도:
   • O(V)O(V)O(V), 최단 거리 배열을 저장하는 데 사용.

 

 

1. 음수 사이클 감지:
   • 음수 가중치가 있는 간선을 포함한 그래프에서, 특정 정점에서 시작하여 음수 가중치 사이클을 감지해야 합니다.
   • 음수 사이클이 존재하면 -1을 출력합니다.
2. 최단 거리 계산:
   • 음수 사이클이 없다면, 시작 정점에서 각 정점까지의 최단 거리를 출력해야 합니다.
   • 도달할 수 없는 노드의 경우 -1을 출력합니다.
3. 입력 조건:
   • 정점(도시)의 개수: 2≤n≤10002 \leq n \leq 1000
   • 간선(버스 노선)의 개수: 1≤m≤50001 \leq m \leq 5000
   • 간선의 가중치 cc: −10000≤c≤10000-10000 \leq c \leq 10000

---

알고리즘 선택

벨만-포드 알고리즘은 다음과 같은 이유로 적합합니다:

1. 음수 가중치가 포함된 그래프에서 최단 거리를 계산할 수 있음.
2. 음수 사이클의 존재를 감지할 수 있음.

---

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

1. 초기화:
   • 시작 정점의 거리를 0으로 설정, 나머지는 INF(무한대)로 초기화.
2. 완화(Relaxation):
   • 모든 간선을 최대 n−1n-1번 반복하며 최단 거리를 업데이트.
   • 간선 (u, v, w)에 대해, dist[v]>dist[u]+wdist[v] > dist[u] + w이면 dist[v]=dist[u]+wdist[v] = dist[u] + w로 갱신.
3. 음수 사이클 확인:
   • 추가 반복에서 거리가 더 줄어들면 음수 사이클이 존재.

---

C++ 코드

#include <iostream>
#include <vector>
#include <tuple>
#include <limits>

using namespace std;

const long long INF = numeric_limits<long long>::max();

int main() {
    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> edges; // 간선 정보 저장
    vector<long long> dist(n + 1, INF); // 최단 거리 테이블

    // 간선 정보 입력
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.emplace_back(a, b, c);
    }

    dist[1] = 0; // 시작 정점의 거리를 0으로 설정

    // 벨만-포드 알고리즘
    for (int i = 1; i <= n - 1; i++) { // 최대 n-1번 완화
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 음수 사이클 확인
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[u] + w < dist[v]) {
            cout << -1 << endl; // 음수 사이클 발견 시 -1 출력
            return 0;
        }
    }

    // 결과 출력
    for (int i = 2; i <= n; i++) {
        if (dist[i] == INF) {
            cout << -1 << endl; // 도달 불가
        } else {
            cout << dist[i] << endl; // 최단 거리
        }
    }

    return 0;
}

---

코드 설명

벨만-포드 알고리즘의 거리 테이블(dist)

• dist[]는 특정 시작 정점(예: 1번 정점)에서 다른 모든 정점까지의 최단 거리를 저장하는 배열입니다.
• 초기값:
  • dist[start] = 0 (시작 정점까지의 거리는 0)
  • dist[other] = INF (시작 정점에서 도달할 수 없는 정점은 무한대)
• 알고리즘 진행 중 dist[]는 반복적으로 업데이트되며, 최단 거리를 점점 줄여 나갑니다.

---

dist[u]와 dist[v]의 의미

• dist[u]: 시작 정점에서 정점 u까지의 현재까지 계산된 최단 거리입니다.
• dist[v]: 시작 정점에서 정점 v까지의 현재까지 계산된 최단 거리입니다.

완화(Relaxation) 과정에서의 역할

if (dist[u] != INF && dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
}

1. dist[u] + w:
   • 시작 정점에서 u를 거쳐 v까지 가는 경로의 새로운 거리.
   • 간선 (u, v)의 가중치가 w일 때, dist[u]+wdist[u] + w는 시작 정점에서 v까지의 거리 후보가 됩니다.
2. dist[v]:
   • 시작 정점에서 v까지의 현재 최단 거리.
3. 조건 dist[u] + w < dist[v]:
   • u를 거쳐 v로 가는 경로가 현재 알려진 최단 거리보다 짧다면, 최단 거리 테이블을 업데이트합니다.

결과:

• dist[v] = dist[u] + w로 갱신.
• 즉, 시작 정점에서 u를 경유하여 v에 도달하는 더 짧은 경로를 발견한 경우, 이를 최단 거리 테이블에 반영합니다.

---

예제

입력:

정점: 4개, 간선: 5개
간선: (1 → 2, 4), (2 → 3, -2), (3 → 4, 2), (4 → 2, 1), (1 → 3, 5)

초기 상태:

• 시작 정점: 1
• 거리 테이블: dist[1] = 0, dist[2] = INF, dist[3] = INF, dist[4] = INF

첫 번째 완화 과정:

• 간선 (1 → 2, 4): dist[1]+4<dist[2]dist[1] + 4 < dist[2] → 0+4<INF0 + 4 < INF → dist[2] = 4
• 간선 (1 → 3, 5): dist[1]+5<dist[3]dist[1] + 5 < dist[3] → 0+5<INF0 + 5 < INF → dist[3] = 5
• 간선 (2 → 3, -2): dist[2]+(−2)<dist[3]dist[2] + (-2) < dist[3] → 4−2<54 - 2 < 5 → dist[3] = 2
• 간선 (3 → 4, 2): dist[3]+2<dist[4]dist[3] + 2 < dist[4] → 2+2<INF2 + 2 < INF → dist[4] = 4
• 간선 (4 → 2, 1): dist[4]+1<dist[2]dist[4] + 1 < dist[2] → 4+1<44 + 1 < 4 → 조건 미충족

. 벨만-포드 알고리즘의 첫 번째 완화 과정에서 각 간선을 순회하며 어떻게 dist 배열(최단 거리 테이블)이 업데이트 과정

---

1. 초기 상태

• dist[] 배열은 시작 정점(1번 정점)에서 다른 정점까지의 거리를 저장합니다.
• 초기 값:
  • dist[1] = 0 (시작 정점은 자기 자신까지의 거리가 0)
  • 나머지 정점들은 아직 도달 불가능하므로 dist[2] = INF, dist[3] = INF, dist[4] = INF.

초기 거리 테이블:

dist[1] = 0
dist[2] = INF
dist[3] = INF
dist[4] = INF

---

2. 첫 번째 간선: (1 → 2, 가중치 4)

• 간선: 1→21 \to 2, 가중치 44.
• 조건: dist[1]+4<dist[2]dist[1] + 4 < dist[2]
  • dist[1]=0dist[1] = 0, dist[2]=INFdist[2] = INF.
  • 계산: 0+4<INF0 + 4 < INF, 참이므로 dist[2]dist[2]를 갱신.
• 갱신: dist[2]=4dist[2] = 4.

거리 테이블 갱신 후:

dist[1] = 0
dist[2] = 4
dist[3] = INF
dist[4] = INF

---

3. 두 번째 간선: (1 → 3, 가중치 5)

• 간선: 1→31 \to 3, 가중치 55.
• 조건: dist[1]+5<dist[3]dist[1] + 5 < dist[3]
  • dist[1]=0dist[1] = 0, dist[3]=INFdist[3] = INF.
  • 계산: 0+5<INF0 + 5 < INF, 참이므로 dist[3]dist[3]를 갱신.
• 갱신: dist[3]=5dist[3] = 5.

거리 테이블 갱신 후:

dist[1] = 0
dist[2] = 4
dist[3] = 5
dist[4] = INF

---

4. 세 번째 간선: (2 → 3, 가중치 -2)

• 간선: 2→32 \to 3, 가중치 −2-2.
• 조건: dist[2]+(−2)<dist[3]dist[2] + (-2) < dist[3]
  • dist[2]=4dist[2] = 4, dist[3]=5dist[3] = 5.
  • 계산: 4−2<54 - 2 < 5, 참이므로 dist[3]dist[3]를 갱신.
• 갱신: dist[3]=2dist[3] = 2.

거리 테이블 갱신 후:

dist[1] = 0
dist[2] = 4
dist[3] = 2
dist[4] = INF

---

5. 네 번째 간선: (3 → 4, 가중치 2)

• 간선: 3→43 \to 4, 가중치 22.
• 조건: dist[3]+2<dist[4]dist[3] + 2 < dist[4]
  • dist[3]=2dist[3] = 2, dist[4]=INFdist[4] = INF.
  • 계산: 2+2<INF2 + 2 < INF, 참이므로 dist[4]dist[4]를 갱신.
• 갱신: dist[4]=4dist[4] = 4.

거리 테이블 갱신 후:

dist[1] = 0
dist[2] = 4
dist[3] = 2
dist[4] = 4

---

6. 다섯 번째 간선: (4 → 2, 가중치 1)

• 간선: 4→24 \to 2, 가중치 11.
• 조건: dist[4]+1<dist[2]dist[4] + 1 < dist[2]
  • dist[4]=4dist[4] = 4, dist[2]=4dist[2] = 4.
  • 계산: 4+1<44 + 1 < 4, 거짓이므로 dist[2]dist[2]는 갱신되지 않음.

거리 테이블 상태(갱신 없음):

dist[1] = 0
dist[2] = 4
dist[3] = 2
dist[4] = 4

---

완화 과정 정리

순서대로 처리한 각 간선의 계산 결과:

1. 간선 (1 → 2, 4): 0+4<INF0 + 4 < INF → 갱신: dist[2]=4dist[2] = 4
2. 간선 (1 → 3, 5): 0+5<INF0 + 5 < INF → 갱신: dist[3]=5dist[3] = 5
3. 간선 (2 → 3, -2): 4−2<54 - 2 < 5 → 갱신: dist[3]=2dist[3] = 2
4. 간선 (3 → 4, 2): 2+2<INF2 + 2 < INF → 갱신: dist[4]=4dist[4] = 4
5. 간선 (4 → 2, 1): 4+1<44 + 1 < 4 → 조건 불만족, 갱신 없음.

---

최종 거리 테이블

첫 번째 완화 과정이 끝난 후의 최단 거리 테이블은 다음과 같습니다:

dist[1] = 0
dist[2] = 4
dist[3] = 2
dist[4] = 4

---

추가 참고

• dist[u]와 dist[v]:
  • dist[u]는 시작 정점에서 uu까지의 최단 거리.
  • dist[v]는 시작 정점에서 vv까지의 최단 거리.
  • 간선 (u, v, w)를 완화하는 과정에서 dist[v]는 uu를 거치는 경로를 통해 최단 거리로 갱신될 수 있습니다.
• 갱신 조건:
  • dist[u]+w<dist[v]dist[u] + w < dist[v]: 시작 정점에서 uu를 거쳐 vv까지 도달하는 경로가 기존 최단 거리보다 짧을 경우 갱신.

---

한 문장 요약

첫 번째 완화 과정은 시작 정점에서 다른 정점으로 가는 경로를 탐색하며, 더 짧은 경로가 발견될 경우 최단 거리 테이블을 갱신하는 과정입니다. 😊

거리 테이블:

dist[1] = 0, dist[2] = 4, dist[3] = 2, dist[4] = 4

---

dist[u]와 dist[v] 간의 관계

1. dist[u]:
   • 시작 정점에서 u까지의 최단 거리.
2. dist[v]:
   • 시작 정점에서 v까지의 최단 거리.
3. dist[u] + w:
   • 시작 정점에서 u를 거쳐 v까지 도달하는 거리.
4. 조건:
   • 만약 dist[u] + w가 기존 dist[v]보다 작다면, dist[v]를 갱신합니다.

---

예제 시각화

그래프:

(1) --4--> (2) --(-2)--> (3) --2--> (4)
  \                      ↑
   \--5-->--------------/

거리 업데이트 과정:

1. 1번에서 시작:
   • dist[1] = 0
   • dist[2] = 4
   • dist[3] = 5
   • dist[4] = INF
2. 2번에서 3번으로 업데이트:
   • 간선 (2 → 3): 4+(−2)=24 + (-2) = 2
   • dist[3] = 2
3. 3번에서 4번으로 업데이트:
   • 간선 (3 → 4): 2+2=42 + 2 = 4
   • dist[4] = 4

입출력 예제

예제 1

입력:

4 5
1 2 4
2 3 -2
3 4 2
4 2 1
1 3 5

출력:

4
2
4

설명:

• 정점 1에서 2로 가는 최단 거리: 4 (1 → 2)
• 정점 1에서 3으로 가는 최단 거리: 2 (1 → 2 → 3)
• 정점 1에서 4로 가는 최단 거리: 4 (1 → 2 → 3 → 4)

---

예제 2 (음수 사이클 존재)

입력:

3 3
1 2 4
2 3 -5
3 1 -4

출력:

-1

설명:

• 정점 1 → 2 → 3 → 1로 돌아가는 경로에서 음수 사이클이 존재합니다.
• 따라서 음수 사이클을 감지하고 -1을 출력합니다.

---

예제 3 (도달 불가능한 노드)

입력:

4 3
1 2 3
2 3 4
3 4 5

출력:

3
7
12

설명:

• 정점 1에서 2로 가는 최단 거리: 3 (1 → 2)
• 정점 1에서 3으로 가는 최단 거리: 7 (1 → 2 → 3)
• 정점 1에서 4로 가는 최단 거리: 12 (1 → 2 → 3 → 4)

---

예제 4 (도달 불가능한 노드 포함)

입력:

5 3
1 2 4
2 3 3
3 4 2

출력:

4
7
9
-1

설명:

• 정점 1에서 2로 가는 최단 거리: 4 (1 → 2)
• 정점 1에서 3으로 가는 최단 거리: 7 (1 → 2 → 3)
• 정점 1에서 4로 가는 최단 거리: 9 (1 → 2 → 3 → 4)
• 정점 5는 시작 정점에서 도달할 수 없으므로 -1 출력.

---

입력 형식

• 첫 줄: nn (정점 개수), mm (간선 개수)
• 다음 mm개의 줄: a,b,ca, b, c (간선 시작점 aa, 끝점 bb, 가중치 cc)

출력 형식

• 음수 사이클이 존재하면 -1 출력 후 종료.
• 음수 사이클이 없으면 시작 정점(1번)에서 각 정점(2번~nn번)까지의 최단 거리를 순서대로 출력.
• 도달할 수 없는 정점은 -1 출력.