[algorithm] Bellman-Ford

벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서 하나의 노드에서 모든 노드까지의 최단 경로를 찾는 알고리즘이다.
시간복잡도 : $O(VE)$

• V : 정점의 개수
• E : 간선의 개수

다익스트라 vs. 벨만-포드

다익스트라 알고리즘은 이후에 방문할 음의 가중치 간선을 고려하지 않고 현재 노드에서 가장 최선의 선택을 하므로 양의 가중치만 있는 그래프에서만 최단 경로를 찾을 수 있다.

하지만 벨만-포드 알고리즘은 이후에 방문할 음의 가중치 간선을 고려하여 모든 정점에서 모든 간선을 방문하여 계산하므로 음의 가중치가 있는 그래프에서도 최단 경로를 찾을 수 있다.

다익스트라	벨만-포드
양의 가중치만 있는 그래프	양의 가중치, 음의 가중치가 있는 그래프

구현 (인접행렬로 구현된 그래프)

#include <iostream>
#include <vector>
using namespace std;

#define INF (int)1e9

void bellman_ford(vector<vector<int>>& v, vector<int>& dist) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v.size(); j++) {
            if (dist[j] > dist[i] + v[i][j]) {
                dist[j] = dist[i] + v[i][j];
            }
        }
    }
}

int main() {
    vector<vector<int>> v{
        { 0, 4, -1, 8 },
        { INF, 0, -2, -10},
        { INF, INF, 0, 3 },
        { INF, INF, INF, 0 }
    };
    vector<int> dist({ 0, INF, INF, INF });

    bellman_ford(v, dist);
    for (auto& e : dist) cout << e << "\t";
    cout << endl;
    return 0;
}