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

벨만 포드 알고리즘은 그래프 상에서 최단경로를 찾는 알고리즘이다. 최단경로를 찾는 다른 알고리즘인 다익스트라(Dijkstra)알고리즘과 다른 점은 간선의 가중치가 음수여도 가능하다는 점이다. 다만 다익스트라보다 수행시간이 더 오래걸린다는 단점이 있다. 따라서 간선의 가중치에 음수가 없다면 다익스트라를, 음수가 있다면 벨만 포드를 사용하는게 일반적으로 좋다.

개념

다익스트라 알고리즘이 그리디 알고리즘이였다면, 벨만 포드 알고리즘의 기본 개념은 다이나믹 프로그래밍이다. 즉, 이전에 계산한 최단경로를 이용해 새로운 최단경로를 갱신하는 식으로 동작한다. 예를 들어 시작노드 s에서 v에 이르는 최단경로는 s에서 u까지의 최단경로에 u에서 v사이의 가중치(거리)를 더한 값이다. 

위와 같은 그래프가 있다면, s에서 v로 가는 최단경로는 D(s,v) = D(s,u)+W(u,v) 이다. 즉 s에서 u로 가는 최단경로에 u에서 v로 가는 비용을 더한 것이다. 따라서 1+3+4 = 8 이 될 것이다.

간단한 예를 들었지만 더 복잡한 그래프도 마찬가지로 위 개념을 적용하면 출발정점에서 다른 모든 점으로의 최단경로를 구할 수 있다. 여기서 중요한 점은, 벨만포드 알고리즘은 그래프에 음수 가중치가 사이클(cycle)을 이루고 있는 경우에는 작동하지 않는다는 것이다.

구현

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;
        }
    }
 
    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;
}

[알고리즘] 벨만 포드(Bellman-Ford) 알고리즘 | c++ 벨만포드 구현 (tistory.com)