벨만-포드 알고리즘

특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘.

- 간선의 가중치가 음인 경우에도 사용가능 하다. 

- 음의 사이클이 있는지 확인 할 수 있다.

V : 노드의 갯수

D[i] : 출발점에서 K 정점 까지의 최소 비용 (D[출발] = 0, 나머지는 무한대로 초기화)

1. 모든 간선을 (V - 1)번 확인한다.

D[now] != INF 이고 D[next] > D[now] + W (간선의 가중치) 이면

D[next] = D[now] + W 로 갱신한다.

2. V번째 간선을 확인했을 때 D가 갱신된다면 음의 사이클이 존재한다.

시간복잡도 : O(VE)

    D[1] = 0; // 출발점의 비용은 0
    FOR(i, 1, V) {
        for (info edge : v) { // 간선이 저장된 배열을 V-1번 돌며 확인한다.
            if (D[edge.u] == MAX_INT) continue; // 경로가 없으면 패스
            if (D[edge.v] > D[edge.u] + edge.w) D[edge.v] = D[edge.u] + edge.w; // 값 갱신
        }
    }
    bool flag = false;
    for (info edge : v) { //V 번째 간선 확인
        if (D[edge.u] == MAX_INT) continue;
        if (D[edge.v] > D[edge.u] + edge.w) flag = true; // 값의 갱신이 일어나면 음의 사이클 존재
    }