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

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

시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘.

다익스트라와 다르기 가중치가 음수인 경우에도 사용이 가능하지만, 최적해를 보장하지는 않는다.

=> 벨만-포드 알고리즘을 이용해 가중치가 음수인 사이클을 찾을 수 있다.

 

시간복잡도의 경우 O(nm)

여기서 n은 노드의 개수, m은 간선의 개수.

 

---

과정

시작 노드에서 다른 모든 노드까지의 길이를 모두 추적.

거리의 초기값은 시작노드를 0, 나머지는 INF로 설정하고, 이 값을 계속 줄여나가는 과정을 통해 더 줄일 수 있는 값이 없을 때까지 반복.

위와 같은 그래프가 있다고 가정하자.

 

가장 먼저 파란색 간선을 통해 INF인 값을 줄인다.

 

3에서 4로 가는 간선을 먼저 보자.

3+1 < 7이기 때문에 줄일 수 있고, 4로 줄어들었다.

 

2에서 4로 가는 간선을 보자.

3에서 4로 가는 간선은 Cost가 4, 2에서 4로 가는 간선은 Cost가 5이기 때문에 탐색은 하되, Cost가 변경되지 않는다.

 

2에서 5로 가는 간선을 보자.

2+5 < INF이기 때문에 7로 줄어들었다.

 

이후 4에서 5로 가는 간선을 봤을 때

4+2 < 7이기 때문에 5로 가는 최소 Cost는 6이라는 걸 알 수 있다.

 

뿐만 아니라 1번 노드에서 각 노드로 가는데까지의 최소 Cost를 확인할 수 있다.

---

구현 (C++)

#include <bits/stdc++.h>
using namespace std;

const int INF = INT_MAX;

vector<tuple<int, int, int>> edges;
vector<int> edge_distance[1000001];

void Bellman_Ford(int x, vector<int> (&edge_distance)[1000001], vector<tuple<int, int, int>> &edges)
{
    for (int i = 1; i <= 5; i++)
    {
        edge_distance[i].push_back(INF);
    }
    edge_distance[x].push_back(0);
    for (int i = 1; i <= 4; i++)
    {
        for (auto e : edges)
        {
            int a, b, w;
            tie(a, b, w) = e;
            int minumum_res = min(edge_distance[b].back(), edge_distance[a].back() + w);
            edge_distance[b].push_back(minumum_res);
        }
    }
}

int main()
{

    edges.push_back({1, 2, 2});
    edges.push_back({1, 3, 3});
    edges.push_back({1, 4, 7});
    edges.push_back({2, 5, 5});
    edges.push_back({2, 4, 3});
    edges.push_back({3, 4, 1});
    edges.push_back({4, 5, 2});

    Bellman_Ford(1, edge_distance, edges);

    cout << "<<노드 1부터 각 노드까지의 최단 거리(벨만-포드)>>" << endl;
    for (int i = 1; i <= 5; i++)
    {
        cout << "노드 " << i << "까지의 거리: ";
        if (edge_distance[i].back() == INF)
            cout << "INF" << endl;
        else
            cout << edge_distance[i].back() << endl;
    }
}

노드 a에서 b로 갈 때 가중치가 w인 걸 {a, b, w}로 표현한다고 가정한다.

그래프는 간선리스트 edges에 {a, b, w}의 형태로 저장되어 있다.

 

알고리즘은 n-1번의 라운드로 구성되어 있다.

라운드마다 모든 간선을 살펴보며 그 간선이 거리를 줄일 수 있는지 확인한다.