[그래프]Bellman-Ford-Moore

Bellman-Ford-Moore

한 정점에서 다른 모든 정점들로 가는 최단 거리를 구하는 알고리즘

무방향 그래프 && 음수 가중치 간선 존재 : 사용 불가
방향 그래프 && 음수 가중치 간선 사이클이 없음 : 사용 가능

+

음수 가중치의 간선이 존재할 때, 누적 cost가 계속 감소하는 사이클의 유무를 확인 가능

그래프에 음수 가중치가 존재하지 않으면 dijikstra를 사용하는 것을 권장

시간복잡도

O(VE)

예시 코드

#define pii pair<int, int>
#define MAX_SIZE 100000
#define INF 0x7fffffff

int dist[MAX_SIZE];
vector<pii> v[MAX_SIZE];

bool bellman-ford(int start){
    bool cycle = false;
    
    for (int i = 1; i <= N; i++)    dist[i] = INF;
    dist[start] = 0;
    
    //N 이 된다면 음수사이클
    for (int limit = 1; limit <= N; limit++){
    
        // 모든 정점에 대해 모든 간선을 탐색
        for (int j = 1; j <= N; j++){
            for (pii n : v[j]){
              	// 방문되지 않은 지점에서 출발은 SKIP
                if (dist[j] != INF && dist[n.first] > n.second + dist[j]){
                    dist[n.first] = n.second + dist[j];
                    if (limit == N) cycle = true;
                }
            }
        }
        
    }
    return cycle;
}

int main(){
    // 정점,간선의 수
    int N,M;
    cin >> N >> M;
    
    for (int i=0;i<M;i++){
        int sn,en,w;
        cin >> sn >> en >> w;
        v[sn].push_back(make_pair(en, w));
    }
    
    if (bellman-ford(1)) cout << "-1\n";  //음수 사이클 존재
    else {
        for (int i=2;i<=N;i++){
            if (dist[i] == INF) cout << "-1\n"; //경로가 없음
            else cout << dist[i] << "\n";
        }
    }
}