[알고리즘] Bellman Ford, 벨만 포드 알고리즘

문제 정의

• 한개의 노드에서 다른 노드까지의 최소 비용 구할때
  • 밸만 포드 : O(VE)
  • 문제의 유형에 따라서 적합한 알고리즘 선택
  • Floyd를 사용할경우 O(V^3)
  • 다익스트라 : O(ElgE)
    • 음수의 간선 확인 가능
• 음수로 인한 거리 무한감소 사이클 확인 가능

문제 접근

• 시작 노드에서부터 나머지 노드까지의 거리 배열을 무한대값으로 초기화(dist 배열)
• dist배열의 시작 노드값을 0으로 만듬
• 모든 간선에 대해서, 간선을 지나는 경우 비용이 더 감소할 경우 업데이트
• 위 과정을 노드의 개수만큼 반복
• 마지막 한번 모든 간선에 대해서, 위 과정을 반복
  • 이때 비용이 더 감소하는 경우가 있다면 >> 무한 사이클 확인

시간복잡도

• 모든 간선을 : O(V)
  • 노드의 개수만큼 반복 : O(E)
  • O(V*E)

대표예제 : 백준 11657 타임머신

#include <iostream>
#include <tuple>
#include <vector>
 
using namespace std;
typedef tuple<int, int, int> ti3;
typedef long long ll;
 
const int inf = 1e8+10;
 
// 거리배열 생성
ll dist[510];
ti3 edge[6010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E; cin >> V >> E;
    fill(dist, dist+510, inf);
    
    for(int i=0; i<E; i++){
        int a,b,c; cin >> a >>b >> c;
        edge[i] = {a,b,c};
    }
    
    // 시작노드 0으로 초기화
    dist[1] = 0;
    
    // 모든 간선을 노드 갯수만큼 반복
    for(int j=0; j<V; j++) {
        for(int i=0; i<E; i++) {
            int a,b,c; tie(a,b,c) = edge[i];
            
            // 아직 거치지 않은 점일경우
            if(dist[a] == inf) continue;
            // a점을 거친 경우 거리가 더 작아질경우
            if(dist[b] > dist[a] + c) dist[b] = dist[a] + c;
        }
    }
    
    // 사이클 확인
    for(int i=0; i<E; i++) {
        int a,b,c; tie(a,b,c) = edge[i];
        
        if(dist[a] == inf) continue;
        // a점을 거친 후 거리가 작아질경우 사이클
        if(dist[b] > dist[a] + c) {
            cout << -1 << '\n';
            return 0;
        }
    }
    
    for(int i=2; i<=V; i++) {
        if(dist[i] == inf) cout << -1 << '\n';
        else {
            cout << dist[i] << '\n';
        }
    }
    
    return 0;
}