벨만-포드

음의 간선이 존재할때

특정 노드에서 다른 노드까지의 최단/최적 거리를 구하는 알고리즘

 

다익스트라와는 다르게 음의 가중치가 존재할 수 있다는 조건때문에
우선순위 큐를 사용하지 않고 이중 for문을 N-1번 돌려 최단 경로를 찾는다

이때 양의 사이클 또는 음의 사이클
즉, 돌수록 최적값이 되는 상황이 존재할 수 있다.
따라서 사이클 유무를 항상 확인해주어야한다.
사이클 유무는 N-1개의 간선을 사용한 이후 1번을 더 돌아봄으로써 업데이트가 되는 노드가 있는지를 통해 확인한다.
이와 같은 경우는 사이클을 구성하는 노드들을 저장해두고, 역추적으로 통해 확인해봐야한다.

---

[벨만-포드에서 우선순위 큐를 사용하지 않는 이유]

 

다익스트라에서 PQ를 사용하는 이유는, 지금 당장 가까운 노드부터 확정짓고 탐색하기 위해서이다.

따라서 PQ를 활용한 그리디적인 방식으로 푼다.

 

하지만 음의 간선이 존재할 수 있는 벨만포드에서는 PQ로 확정할 수 가 없다.

따라서 2중 for문을 통해 모든 간선을 업데이트해보는 방식으로 진행된다.중간에 마이너스가 있을지도 모르니까 확신할 수 가 없으므로, 그냥 무식하게 전부 다 훑자는 마인드인 것이다!

 

---

[벨만-포드 동작 방식]

 

간선 정보는 다음과 같다고 가정

간선 정보는 정렬하지 않고 시작해도 된다!

(B,E,2), (D,B,1), (B,D,2), (A,B,-1), (A,C,4), (D,C,5), (B,C,3), (E,D,-3)

 

 

1. 출발 정점은 시작점이니 0으로 두고 시작

 

 

출발 정점의 거리를 제외하고 모든 거리를 INF으로 초기화 ㅇㅇ

 

2. 모든 정점을 간선 정보 순서대로 처리

(B,E,2), (D,B,1), (B,D,2), (A,B,-1), (A,C,4), (D,C,5), (B,C,3), (E,D,-3)

 

모든 모서리가 처음으로 처리될 때 아래와 같은 거리 결과가 나옴

 

행1 은 시작전 거리

 

행2는 (B,E,2), (D,B,1), (B,D,2), (A,B,-1)를 돈 후 결과임

(B,E,2), (D,B,1), (B,D,2)의 결과는 INF이므로 기존 거리에 변함이 없고 (A,B,-1)을 적용한 -1만 반영

 

행3은 (A, C,4)가 처리된 후의 결과

 

행4는 (D, C,5), (B, C,3), (E, D,-3)이 처리된 후의 결과임

 

이번이 첫번째 순회이므로 각 노드가 간선을 한번만 고려한 결과임!

 

3. 2번을 한번 더 반복하면서 간선 두 개를 고려했을때의 각 노드까지의 최단거리를 구하기

 

모든 정점이 두 번째로 처리 될 때 아래와 같은 결과값을 얻는다.

 

 

두번째 반복은 최대 2개의 간선으로 각 노드까지 갈 수 있는 최단 경로의 결과임!

 

---

[주의 사항]

 

Bellman-Ford 알고리즘을 사용할 경우 아래와 같은 음의 가중치 주기를 주의해야함!

위의 예제는 1 → 2 → 3 순서를 계속 반복하면 최단거리가 계속 줄어들어 N-1번 이후에도 계속 최신화됨!

 

→ 즉, 답을 낼 수 없는 경우임

 

따라서 N-1번 돌린 이후 한번 더 돌려서 음의 사이클의 존재성을 꼭 확인해봐야함.

 

만약 1번 더 돌렸을때 업데이트가 일어난다면 음의 가중치가 포함되어있다는 의미임!

 

---

[다익스트라와의 차이점?]

 

다익스트라는 우선순위 큐를 이용하여

지금 당장 눈앞에 보이는(Heap에 들어간 노드들 중),

연결되어 있는 정점들 중 최소비용으로 연결된 정점을 선택하는 그리디 방식으로 접근해서

각 노드까지의 최단거리를 매 순간마다 최신화하며

다른 노드까지의 최단거리를 구해나감

 

하지만 벨만포드는 다익스트라와 달리 그리디 하지 않게 동작한다

매 턴마다 모든 경우의 수를 탐색하는 동작원리를 가지고 있다

 

벨만포드는 매 단계마다 모든 간선을 전부 확인하여

한 개의 노드에서 다른 노드까지의 최단거리를 구해나감

 

---

[양의 사이클 예시]

이건 양의 사이클임

최대 경로를 찾을때 양의 사이클을 조심해야함

돌면 돌수록 이득이기 때문임

 

---

[음의 사이클 예시]

이게 bellmanford에서 말하는 음의 사이클임
사이클의 총 가중치 합이 음수인거

 

음의 사이클이 포함된 최단경로 찾기에서는
음의 사이클을 돌때마다 개이득임

매번 음수인 가중치가 추가적으로 부여되므로 돌때마다 최단거리가 최신화됨
 
→ bellmanford가 음의 사이클을 잡는다는게 이런류의 사이클을 잡겠다는거임

 

---

[Cycle이 존재하는 경우의 예외처리]

 

보통 벨만포드를 사용하는 경우에

벨만포드로 인해 나온 최적의 경로에

사이클의 존재성을 판별해야할 경우가 많음
 

따라서 벨만포드 이후에 BFS를 따로 실행해서

최적의 경로에 사이클을 형성하는 노드들이 존재하는지 확인해줘야함

 

1. 벨만포드 돌릴때 cycle을 형성하는 노드들을 저장해둔다

2. 벨만포드 이후 BFS를 실행하여 사이클을 형성하는 노드들로부터 종점까지 길이 있는지 확인한다

 

https://www.acmicpc.net/problem/1738

https://www.acmicpc.net/problem/1219

 

---

[Cycle과 최적경로의 관계에 대한 경우의 수]

 

1. cycle이 존재하지 않는다

 

2. cycle이 존재하는데 도달하지 못하는 경우

시작점에서 사이클까지 도달하지 못하는 경우에는 신경을 안써도 된다

 

왜냐하면 벨만포드는 시작점만 0으로 해놓고 시작하는데

벨만포드가 돌아가면서 도달할 수 있는 정점들은 모두 초기값 INF/INT_MIN이 아닌 다른 값들로 모두 초기화가 되기 때문이다.

 

따라서 시작점에서 도달못하는 노드들은

벨만포드가 끝나도, 사이클 검사를 할때도,

언제나 기본 초기값인 INF 또는 INT_MIN이기 때문에

continue 구문을 통해 알아서 스킵하게 된다.

 

3. cycle이 존재하고 최적경로 내 포함 O

이 경우에는 벨만포드 이후에 cycleNode_set에 3,4,5번이 저장되어 있을 것이다.

따라서 이 3,4,5번을 queue에 넣고 BFS를 돌려서 6이 나오는지 확인해주면 된다.

 

종점까지 갈 수 있으니 6이 나온다.

 

 

4. cycle이 존재하고 최적경로 내 포함 X

이 경우에도 벨만포드 이후에 cycleNode_set에 3,4,5번이 저장되어 있을 것이다.

따라서 이 3,4,5번을 queue에 넣고 BFS를 돌려서 6이 나오는지 확인해주면 된다.

 

종점까지 갈 수 없으니 6은 안나오고 queue가 비면 끝날 것이다.

---

[bellman_ford의 최종 결과는 같지만 간선이 저장된 순서에 따라 각 순회에서의 결과가 달라질 수 있다]

 
답이 첫번째 순회에서 한큐에 바로 나올 수 도 있고
답이 마지막 순회에 완성될 수 도 있고
중간에 완성될 수 도 있다
 
그 이유는 bellman ford에서 for(0, N-1) 만큼 돌면서 dist 배열을 최신화하는데
이때 특정 정점의 dist 최신화가 늦게 되어 그 전에 반영될 수 있었던게 반영안되었을 수 도 있기 때문임
 
이렇게 생각하면 된다
 
일단 초기에는 모두 최단거리가 INF이고 구해진 최단거리가 작으면 최신화하는데
원래 INF였던 놈이 있는데 얘가 값이 INF라 얘 때문에 최신화가 못된 애들이 있었을 수 있음.
근데 얘가 맨 마지막에 최신화가 됨.
그럼 담턴에 그 전에 얘가 INF여서 최신화 못됐던 애들이 최신화가 될 수 있는 구조인거임
 
근데 만약 얘가 좀 앞순에 있어서 일찍 다른 값으로 최신화가 되었다?
그럼 그 턴에 다른 애들도 얘 덕에 최신화가 되었을 수 있었던거임.
 
따라서 간선이 저장된 순서에 따라 알고리즘 수행 과정에서의 결과값은 달라질 수 있다.
 

---

[간선을 N-1번 순회하는 이유]

    // 최대 간선 개수인 N-1번 만큼 돌리기
    int start, end, cost;
    for (int i = 0; i < N - 1; i++)
    {
        for (int k = 0; k < M;k++){

 

여기서 i의 의미는 경로에 포함된 간선의 갯수이다.

 

i = 1 일때는 간선 하나일때 시작점에서 특정 지점까지 갈 수 있는 최적거리

i = 2 일때는 간선 두 개일때 시작점에서 특정 지점까지 갈 수 있는 최적거리

...

...

i = N-1 일때는 간선이 N-1 개일때 시작점에서 특정 지점까지 갈 수 있는 최적거리

인 것이다.

 

따라서 그래프에서 한 정점에서 다른 정점까지의 최대 간선의 갯수는 N-1개 이므로 N-1개까지만 돌리는 것이다.

 

근데 여기서 한번 더 돌렸는데 특정 노드에서 새로운 최적의 거리가 나왔다면?

그 의미는 음의 사이클이 존재한다는 것이다.

 

사이클이 없다면, 최대 간선의 갯수 내에서 최적의 거리가 나올 것이다.

하지만 간선 하나가 더 있는 경우를 고려하였는데 새로운 최적의 거리가 나왔다면

그것은 그래프 내에 사이클이 존재한다는 의미이다.

 

따라서 N-1개의 간선을 고려한 뒤,

마지막에 한번 더 for 문을 돌려 사이클 유무를 판별해줘야한다.

 

---

#include <iostream>
#include <climits>
#include <unordered_set>
#include <bitset>
#include <vector>
#include <queue>
#define SIZE 101

using namespace std;

int N, M;
vector<pair<pair<int, int>, int>> v;
unordered_set<int> cycleNodes;
vector<vector<int>> graph(SIZE);

int dist[SIZE];

void solve()
{
    // 모든 거리 초기화
    for (int i = 0; i <= N;i++)
        dist[i] = INT_MIN;
    // 시작점 초기화
    dist[1] = 0;

    // 최대 간선 개수인 N-1번 만큼 돌리기
    int start, end, cost;
    for (int i = 0; i < N - 1; i++)
    {
        for (int k = 0; k < M;k++){
            start = v[k].first.first;
            end = v[k].first.second;
            cost = v[k].second;

            if(dist[start] == INT_MIN) continue;

            if(dist[start] + cost > dist[end]){
                dist[end] = dist[start] + cost;
            }
        }
    }

    // 양의 사이클 존재성 검사
    // 최대 간선만큼 돌린 거에서 한번 더 돌려서 업데이트되는 간선이 있으면 사이클이 있다는거
    // 해당 사이클을 거쳐서 종점까지 갈 수 있는지 없는지까지 검사는 밖에서
    for (int k = 0; k < M; k++)
    {
        start = v[k].first.first;
        end = v[k].first.second;
        cost = v[k].second;

        if (dist[start] == INT_MIN)
            continue;

        if (dist[start] + cost > dist[end])
        {
            cycleNodes.insert(start);
        }
    }
}

// 사이클이 종점가는 경로에 존재하는지 확인
bool checkIfCycleInRoute(){
    queue<int> q;
    bitset<SIZE> visited;
    for (int node : cycleNodes)
    {
        q.push(node);
        visited[node] = 1;
    }

    int cur, next;
    while (!q.empty())
    {
        cur = q.front();
        q.pop();

        for (int i = 0; i < graph[cur].size();i++){
            next = graph[cur][i];

            // 종점까지 갈 수 있다면
            if(next == N){
                return true;
            }

            if(!visited[next]){
                q.push(next);
                visited[next] = 1;
            }
        }
    }

    // 종점까지 못가면
    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;

    int start, end, cost;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end >> cost;
        v.push_back(make_pair(make_pair(start, end), cost));
        graph[start].push_back(end);
    }

    // 벨만포드
    solve();

    // 아예 종점까지 못가는 경우
    if(dist[N] == INT_MIN){
        cout << "아예 종점까지 못가는 경우" << "\n";
        cout << -1;
        return 0;
    }

    // 종점가는 길에 양의 사이클 존재할 경우
    if(checkIfCycleInRoute()){
        cout << "종점가는 길에 양의 사이클 존재할 경우" << "\n";
        cout << -1;
        return 0;
    }

    // 종점까지의 최적경로 값 출력
    cout << dist[N];

    return 0;
}