[알고리즘] 벨만 포드 알고리즘

다익스트라 알고리즘은 그래프에 음수 가중치가 있을 때 올바른 결과를 보장할 수 없다.

왜냐하면 항상 현재까지 가장 짧은 거리를 갖는 노드를 선택하는 그리디 알고리즘이기 때문이다.

게다가 음수 사이클이 존재할 경우 가중치가 계속 내려가기 때문에 무한히 사이클을 순환할 수 있다.

이를 보완하기 위해 시간복잡도는 조금 크지만 사용하는 것이 벨만 포드 알고리즘이다.

 

https://yabmoons.tistory.com/365

[ 벨만포드 알고리즘 ] 개념과 구현방법 (C++)

벨만포드 알고리즘은 출발 정점이 한번이라도 계산된 정점이라면 해당 간선이 잇는 정점의 거리를 비교해서

업데이트한다.

 

void Bellman_Ford()
{
    Dist[1] = 0;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < Edge.size(); j++)
        {
            int From = Edge[j].first.first;
            int To = Edge[j].first.second;
            int Cost = Edge[j].second;
 
            if (Dist[From] == INF) continue;
            if (Dist[To] > Dist[From] + Cost) Dist[To] = Dist[From] + Cost;
        }
    }

먼저 출발정점 하나를 정해 dist를 0으로 설정하고 Dist[출발정점]이 계산된 경우 (Dist[출발정점]이 INF가 아닐 때)

출발정점과 이어져있는 도착정점의 거리를 업데이트한다. 이를 N-1번 반복한다.

N은 정점개수인데, N-1번 반복하는 이유는 최단 경로는 정점을 최대 정점 개수 -1개만큼 거칠 수 있기 때문이다.

루프 한번당 정점으로부터 이어져있는 다른 정점까지 거리를 구하기 때문에 최대 N-1번이면 최단경로를  구할 수 있다.

 

 for (int i = 0; i < Edge.size(); i++)
    {
        int From = Edge[i].first.first;
        int To = Edge[i].first.second;
        int Cost = Edge[i].second;
 
        if (Dist[From] == INF) continue;
        if (Dist[To] > Dist[From] + Cost)
        {
            cout << "음의 사이클이 존재하는 그래프입니다." << endl;
            return;
        }
    }
    cout << "음의 사이클이 존재하지 않는, 정상적인 그래프 입니다." << endl;
}

 N-1번 루프가 끝난 뒤에도 한번 더 루프를 진행하는데 그 이유는 음수 사이클 존재 여부를 판단하기 위해서이다.

여기서도 최단 경로가 갱신된다면 최단 경로가 음의 무한인 음수 사이클이 존재하는 것이다.