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

 

 

벨만-포드 알고리즘

벨만 포드 알고리즘은 그래프에서 출발점이 주어졌을 때 최단 거리를 계산하기 위한 알고리즘입니다.

 

그렇다면 다익스트라 알고리즘과는 무슨 차이가 있을까요?

다익스트라 알고리즘을 수행하기 위해서는 그래프의 모든 간선이 음이 아닌 가중치를 가져야 한다는 조건이 지켜져야 합니다.

그에 반면 벨만포드 알고리즘은 그래프 내 음의 가중치를 갖는 간선이 있어도 수행가능한 알고리즘 입니다.

 

다익스트라 알고리즘에서 음의 가중치를 가진 간선이 존재하면 왜 수행하지 못할까요?

음수 가중치가 있으면 이전까지 계산해둔 최단거리가 최소값이라는 보장을 받을 수 없기 때문입니다.

또한 음수 사이클이 발생하면 최단거리가 무한히 줄어들게 됩니다.

그렇기 때문에 벨만 포드 알고리즘으로 더 많은 연산을 통해 음수 사이클을 탐지하고, 최단 거리를 탐색해야 합니다.

 

 

동작 원리

다익스트라처럼  해당노드까지의 거리 + 간선의 가중치 = 다음 노드까지의 거리 형태로 최단거리를 구해나갑니다.

당연하지만 해당 노드까지의 거리가 아직 정의되지 않아 $\infty$라면 아직 계산할 수 없습니다.

단계마다 출발점으로부터의 거리가 가장 짧은 노드의 간선만 확인하는 다익스트라와 달리,

매 단계마다 모든 간선을 확인 해야 합니다. 

 

첫번째 단계에선 시작노드로부터 뻗어나오는 간선만을 계산하게 되고 (나머지 노드들은 모두 무한대),

두번째 단계에선 이전 단계에서 계산되어 새로 정의된 거리($\infty$가 아닌)를 갖는 노드가 가진 간선을 계산할 수 있게 되고, 세번째 단계에서도 이전 단계에서 계산된... 

 

 

그럼 이제 각 단계를 몇 번 반복해야 하는지 알아봅시다.

다시 말하면 각 단계를 몇 번 반복해야 모든 노드들의 최단거리가 최소임을 보장받을 수 있을까요?

 

단순히 생각한다면 

이런 상황에서 v(노드의 개수) - 1 만큼은 반복해야 1번부터 5번까지의 최단거리를 구할 수 있습니다.

 

v-1 은 그래프에서 사이클 없이 한 노드에서 모든 노드까지 도달할 수 있는 최소 간선의 개수입니다. (트리의 간선의 개수)

최단 거리를 사이클이 없어야 하니,

 v-1 번 각 단계에서 모든 간선을 확인하며 최단거리를 업데이트해 나가면, 시작 노드에서 연결되어 있는 모든 노드들의 최단거리를 구할 수 있습니다.

 

 

앞서 설명했던 내용들을 예시를 들어 직접 적용해 봅시다.

위와 같은 그래프가 주어지고 출발점은 1번 노드입니다.

출발노드를 제외하고 모든 노드들까지의 거리를 $\infty$로 저장합니다.

	1	2	3	4	5
Distance	0	INF	INF	INF	INF

 

각 단계마다

Distance[from] != INF 인 노드들의 간선을 탐색하여 

distance[dest] > distance[from] +  weight 를 만족한다면 값을 갱신해줍니다.

 

 

1번째 반복 - 1번 노드

	1	2	3	4	5
Distance	0	3	5	1	INF

1번 노드의 간선들에 대해 업데이트

 

 

 

2번째 반복 - 1번 노드

1번 노드에 대해서 변경 사항 없음

 

 

2번째 반복 - 2번 노드

	1	2	3	4	5
Distance	0	3	5	1	3 + 4 = 7

2 ->3 변동사항 없음 ( 5 < 3 + 6)

 

 

2번째 반복 - 3번 노드

	1	2	3	4	5
Distance	0	3	5	1	5 - 3 = 2

3 -> 4 변동 없음 (1 < 5 - 2)

 

 

2번째 반복 - 4번 노드

	1	2	3	4	5
Distance	0	1 - 2 = -1	5	1	1 - 1 = 0

 

 

 

 

3번째 반복 - 1, 2, 3, 4번 노드

변동사항 없음

 

3번째 반복 - 5번 노드

	1	2	3	4	5
Distance	0	-1	5	1	0

간선 없음

 

 

 

4번째 반복 - 1, 2번 노드

1번 노드 변동사항 없음

만약 2 -> 3의 가중치가 6이 아닌 5 였다면 Distance[3] = -1 + 5 = 4로 업데이트 되었을 것입니다.

이처럼 음수 가중치에 의해서 이전에 저장되었던 최단거리가 새로운 최단거리로 변경되어

다시 그 노드와 연결된 다른 노드들까지의 거리를 꼭 확인해야 합니다.

 

처음부터 좋은 예시가 될 수 있는 그래프를 사용할 걸 하는 후회가 드네요.

 

 

 

4번째 반복 - 3, 4, 5번 노드

변동사항 없음

 

 

 

5번째 반복

변동사항 없음

 

 

 

최종 Distance

	1	2	3	4	5
Distance	0	-1	5	1	0

 

 

벨만 포드 알고리즘은 최단 거리를 계산하기도 하지만 음수 사이클 발생을 검사할 수도 있습니다.

 

v-1 번 반복으로 사이클이 없을 경우를 가정하고 최단거리를 계산했습니다.

여기서 한 번 더 반복했을 때 distance에 갱신되는 값이 있다면 음수 사이클이 발생했다는 것을 알 수 있습니다.

 

 

연습문제로 [백준] 11657 타임머신을 풀어볼 수 있습니다.

 

코드

#include <iostream>
#include <vector>

#define INF INT32_MAX 

using namespace std;

struct Edge
{
    int from;
    int dest;
    int weight;
};

int main()
{
    int n = 5;
    vector<Edge> edges;
    vector<int> dist;

    dist.assign(n+1, INF);

    edges.push_back({1, 2, 3});
    edges.push_back({1, 3, 5});
    edges.push_back({1, 4, 1});
    edges.push_back({2, 3, 6});
    edges.push_back({2, 5, 4});
    edges.push_back({3, 4, -3});
    edges.push_back({3, 5, -3});
    edges.push_back({4, 2, -2});
    edges.push_back({4, 5, -1});
    
    dist[1] = 0;
    for (int i=0; i<n-1; ++i) 
    {
        for (Edge e : edges)
        {
            int from = e.from;
            int dest = e.dest;
            int weight = e.weight;

            if (dist[from] == INF)
                continue;
            
            if (dist[dest] > dist[from] + weight)
                dist[dest] = dist[from] + weight;
        }
    }

    for (int i=1; i<n+1; ++i)
    {
        cout << "dist[" << i << "] : " << dist[i] << endl;
    }

    vector<int> answer = dist;

    // 음의 사이클 검사
    for (Edge e : edges)
    {
        int from = e.from;
        int dest = e.dest;
        int weight = e.weight;

        if (dist[from] == INF)
            continue;
        
        if (dist[dest] > dist[from] + weight)
            dist[dest] = dist[from] + weight;
    }

    bool isCycle = false;
    for  (int i=1; i<n; ++i)
    {
        if (answer[i] != dist[i])
        {
            isCycle = true;
            break;
        }
    }

    if (isCycle)
        cout << "Cycle == true" << endl;
    else
        cout << "Cycle == false" << endl;

    return 0;
}

 

결과