벨만-포드 알고리즘(Bellman-Ford’s algorithm)

여기 설명이 워낙 좋아서 한 번 보면 이해되고, 그렇게 어려운 알고리즘도 아니다.

다익스트라와 비슷하게, 하나의 정점에서 다른 모든정점으로의 최단거리를 한번에 구해주지만, 

약간은 느린편이고, 

대신 negative edge에 대해서도 처리가 가능하다.

PS용으로 내가 사용하는 코드는 다음과 같다.

(백준11657문제의 답안이기도 하다.)

참고로 정점과 간선의 정보를 표현하는데는 인접행렬과 인접리스트 두 가지 방식이 있는데,

아래는 좀 더 범용적으로 사용할 수 있는 인접리스트 방식을 사용했다.

예를 들어 정점간 간선이 하나가 아니라 여러개일 때는 인접리스트는 표현이 쉽지만 인접행렬은 좀 애매하다.

#include <bits/stdc++.h>
using namespace std;
 
const int INF = INT_MAX / 4;
struct node { int v, w; };
 
vector<int> bellman_ford(int max_v, int start_v, vector<vector<node>>&adj_list) {
    //모든 정점의 최단 경로를 무한대로 초기화
    vector<int> dist(max_v+1, INF);
    //시작정점만 0으로 초기화
    dist[start_v] = 0;
    for (int t = 0; t < max_v - 1; t++) {//N-1번 업데이트 수행
        for (int j = 1; j <= max_v; j++) {//모든 노드에 대해
            for (node adj : adj_list[j]) {
                //무한대가 아니면
                if (dist[j] == INF) continue;
                //최소값으로 업데이트
                dist[adj.v] = min(dist[adj.v], dist[j] + adj.w);
                int sfsd = 1;
            }
        }
    }
    //한번더 업데이트 시도해서
    for (int j = 1; j <= max_v; j++) {//모든 노드에 대해
        for (node adj : adj_list[j]) {
            if (dist[j] == INF) continue;  // 고립된건 무한대일수 있음
            //업데이트가 일어나면
            if (dist[adj.v] > dist[j] + adj.w) {
                //네거티브 사이클이 있는것
                printf("-1\n"); exit(0);  // 코드 재활용시 이부분 주의
            }
        }
    }
    return dist;
}
 
int main()
{
    int N, M; scanf("%d%d", &N, &M);
    vector<vector<node>> adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        adj_list[u].push_back({ v,w });
        //adj_list[v].push_back({ u,w });
    }
 
    vector<int> dist = bellman_ford(N, 1, adj_list);
    for (int i = 2; i <= N; i++) {
        printf("%d\n", dist[i] == INF ? -1 : dist[i]);
    }
    return 0;
}

시간복잡도

복잡도는 정점의 개수가 $V$ 이고 간선의 개수가 $E$일때 $O(VE)$가 되며,

directed graph기준으로 모든 정점간 간선이 꽉차있다고 하면 $E = (V-1)^2$이 되어 $O(V^3)$이 된다.

근데 보통 간선이 꽉차있지 않고, undirected라고 하더라도 간선의 개수가 sparse 하지만 않다면, 

복잡도로 치면 $O(E) = O(V^2)$이 되는 경우가 일반적이라서 전체적인 벨만포드의 복잡도는 $O(V^3)$정도로 보면 된다.(다익스트라가 $O(V^2)$미만으로 계산되는데 비해서 비싼편)