최단 경로 알고리즘 - 2. 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

최단 경로(shotest path)를 찾는 알고리즘으로,
시작 노드에서 다른 노드들 사이의 최단 경로를 찾는 알고리즘이다.

 

특징

• 가중치가 음수 일 때도 사용이 가능
• 음수 사이클 감지 가능
• 시간 복잡도 : O(VE)

 

벨만포드 vs 다익스트라

다익스트라

• 그리디 방식 - 매번 방문하지 않은 노드 중, 최단 거리 노드 선택
• 음수 간선이 없다면 최적해를 찾을 수 있다.

 

벨만포드

• 매번 모든 간선을 확인 (따라서 모든 간선이 양수일 경우 다익스트라 알고리즘이 더 빠르다)
  • 따라서 다익스트라 알고리즘의 최적해를 항상 포함
• 음수 간선이 포함된 경우 음수 사이클을 탐지할 수 있다.

 

핵심 아이디어

거쳐가는 노드를 기준으로 가능한 모든 노드 쌍의 최단 거리를 갱신해 나간다.

 

알고리즘

1. 시작 노드 설정
2. 최단 거리 테이블 초기화
3. 다음 과정을 N - 1 번 반복
   1. 전체 간선 E개를 하나씩 확인
   2. 각 간선을 거쳐서 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

 

*음수 간선 순환이 발생하는지 확인하는 방법

• 위 과정에서 3번 과정을 한번 더 수행
• 이때 최단 거리 테이블 갱신이 이뤄진다면 음수 사이클이 존재

 

<참고> sudo code

sudo code

*RELAX : '줄이다' - 더 낮은 가중치로 갱신

 

 

구현 코드

[BOJ- 11657] 타임머신

#include <iostream>
#include <vector>

using namespace std;

const int INF = 987654321;
const int MAX = 500;

int N, M;

struct Edge
{
    int u, v, w;
};

vector<Edge> edge;
long long dist[MAX + 1];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge.push_back({ u,v,w });
    }

    for (int i = 1; i <= N; i++) {
        dist[i] = INF;
    }

    dist[1] = 0;

    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < M; j++)
        {
            int u = edge[j].u;
            int v = edge[j].v;
            int w = edge[j].w;

            if (dist[u] == INF) continue;

            if (dist[v] > dist[u] + w) dist[v] = dist[u] + w;
        }
    }

    for (int i = 0; i < M; i++)
    {
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;

        if (dist[u] == INF) continue;
        if (dist[v] > dist[u] + w)
        {
            cout << -1 << '\n';
            return 0;
        }
    }

    for (int i = 2; i <= N; i++)
    {
        if (dist[i] == INF) cout << -1 << '\n';
        else cout << dist[i] << '\n';
    }

    return 0;
}

 

References

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