벨만-포드(bellman-ford) 알고리즘

벨만 포드 알고리즘이란? 

벨만 포드 알고리즘은 다익스트라 알고리즘과 다른 점이 하나 있습니다.

다익스트라 알고리즘은 임의의 한 정점에서 다른 정점까지 가는 최소 비용을 구하는 알고리즘입니다. 이때, 간선의 가중치는 양수입니다. 하지만, 벨만-포드 알고리즘은 다익스트라 알고리즘과 정의는 같지만, 간선의 가중치가 음수가 되는 경우도 있습니다. 다익스트라 알고리즘 모르시는 분들은 참고하실 수 있도록 해당 링크 남기겠습니다. 

https://daily1313.tistory.com/237

다익스트라(Dijkstra) 최단 경로 알고리즘

 

그러면 왜 다익스트라 알고리즘으로 해결하지 못하는가?

1번 정점에서 4번 정점으로 가기 위한 최소비용을 예시를 들어보겠습니다. 

다음과 같이 음수 간선의 순환이 포함된다면(2->3->5), 다익스트라 알고리즘을 적용하면 음수 사이클이 발생하게 됩니다. 그래서 시작점에서 도착점까지 가는 경로 중에서 중간에 존재하게 된 음수 순환 때문에, 최소비용은 음의 무한대가 되기 때문에 다익스트라 알고리즘을 적용할 수 없게 됩니다. 

그래서 간선의 가중치가 음수인 경우에는 벨만-포드 알고리즘을 적용해야 합니다.

 

음수 간선에 관하여 최단 경로 문제의 경우의 수는 총 3개가 있습니다.

1.  모든 간선이 양수인 경우
2.  음수 간선이 있는데, 순환이 없는 경우
3.  음수 간선도 존재하고, 순환도 존재하는 경우

즉, 벨만-포드 알고리즘을 적용하게 되면, 음수 간선의 순환을 감지할 수 있고 시간 복잡도는 O(VE)가 됩니다.

 

벨만-포드 알고리즘 동작 과정

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 다음 과정 N-1번 반복
   • 전체 간선 E개를 하나씩 확인(다익스트라는 임의의 정점과 연결된 간선만 검사하기에 시간 복잡도는 벨만-포드 알고리즘이 높다)
   • 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
4. 만약 음수 간선 순환이 발생하는지 체크하고 싶으면, 3번의 과정을 한 번 더 수행한다(최단 거리 테이블 갱신 시 음수 간선 순환 존재)

 

다익스트라(dijkstra) 알고리즘 vs 벨만-포드 알고리즘

 

다익스트라 알고리즘

• 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
• 음수 간선이 없다면 최적해를 찾을 수 있습니다.

벨만 포드 알고리즘

• 매번 모든 간선을 전부 확인합니다.
  • 따라서, 다익스트라 알고리즘에서의 최적해를 항상 포함
• 다익스트라 알고리즘에 비해서 시간이 오래 걸리지만, 음수 간선 순환을 탐지할 수 있습니다.

<코드>

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int INF = 2100000000;
const int MAX = 501;
int n, m;
long long dist[MAX];
vector<pair<int, int>> graph[MAX];
bool cycle;
void bellmanFord(int start)
{
    fill(dist, dist + n + 1, INF);
    dist[start] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (auto p : graph[j])
            {
                int next = p.first;
                int cost = p.second;
                if (dist[j] != INF && dist[next] > dist[j] + cost)
                {
                    dist[next] = dist[j] + cost;
                    if (i == n) cycle = true; 
                    // 음수 사이클 존재
                    // i == n일 때, n번째 루프가 돌고 있는 상태입니다. 이 루프는 최대 n-1번 돌게 되어 있으며, 이것은 그래프의 모든 정점들 간의 최단 경로를 구하기 위해 최대 n-1개의 간선을 사용하기 때문입니다.
                    // 그러나 n번째 루프는, n-1개의 간선을 사용한 최단 경로를 더 개선할 수 있는 음수 사이클이 있는지 검사합니다. 즉, n번째 루프가 끝나는 시점에서 n개의 간선을 사용한 경로에서 최단 거리를 구할 수 있는 경우, 음수 사이클이 존재한다는 것을 의미합니다.
                    // 그렇기 때문에 i == n일 때, true를 반환하여 음수 사이클이 존재한다는 것을 알리는 것입니다.
                }
            }
        }
    }
}

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

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
    }
    bellmanFord(1);
    if (cycle)
        cout << -1;
    else
    {
        for (int i = 2; i <= n; i++)
        {
            if (dist[i] == INF)
                cout << -1 << '\n';
            else
                cout << dist[i] << '\n';
        }
    }

    return 0;
}