[Algorithm] 벨만-포드(Bellman-Ford) 알고리즘(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 한 도시에서 다른 도시로 이동하는데 쓰이는 비용의 최솟값

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

ㅇ벨만-포드 알고리즘

  - 최소 비용으로 출발 정점에서 도착 정점까지 가는 경로를 탐색

  - 간선을 한 개부터 (정점 개수 - 1)개 만큼 사용해보면서 최소 비용을 탐색

    (간선을 정점개수만큼 사용해서 최소 비용이 나온다면? 이것은 음의 사이클이 존재하는 것)

  - 음의 사이클이 존재 X (방문한 정점을 사이클로 계속 방문하면서 거리 비용이 줄어드는 경우)

    아래 그래프에서 2 -> 3 이 -9 일 때, 음의 사이클이 생기게 됨

제일 중요한 과정을 그려보면서 이해해보자.

실제로는 1차원 배열을 사용해도 되지만,

쉬운 이해(?)를 위해 2차원 배열을 사용하여 과정을 그려보자.

1열은 간선 사용 개수, 1행은 정점 번호를 의미한다.

우선 처음 거리 비용은 무한대로 초기화 하자.(최소 비용을 구해야 하므로)

-- 를 무한대로 표시, 그리고 정점1은 시작점이므로 최소 비용을 0으로 초기화

시작 정점이 1이고 도착 정점이 5라고 가정하였을 때,

	1	2	3	4	5
	0	--	--	--	--
1
2
3
4

먼저 간선을 한 번만 사용해서 갈 수 있는 경로 비용을 계산해보자.

먼저 정점 1부터,

정점1 -> 정점2 : +5 의 비용이 든다(0 + 5). 정점2의 현재 비용(무한대)보다 5가 더 작으므로 5를 기록

정점1 -> 정점3 : +4 의 비용이 든다(0 + 4). 정점3의 현재 비용(무한대)보다 4가 더 작으므로 4를 기록

다음 정점 2,

정점2 -> 정점3 : -3 의 비용이 든다(-- + -3). 정점3의 현재 비용(무한대)보다 -- -3 이 더 작은데 그냥 --로 표시

정점2 -> 정점5 : +13 의 비용이 든다(-- + 13). 정점5의 현재 비용(무한대)보다 더 크므로 갱신하지 않음

다음 정점 3,

정점3 -> 정점4 : +5 의 비용이 든다(-- + 5). 정점4의 현재 비용(무한대)보다 더 크므로 갱신하지 않음

다음 정점 4,

정점4 -> 정점2 : +3 의 비용이 든다(-- + 3). 정점2의 현재 비용(무한대)보다 더 크므로 갱신하지 않음

정점4 -> 정점5 : +7 의 비용이 든다(-- + 7). 정점5의 현재 비용(무한대)보다 더 크므로 갱신하지 않음

기존 비용보다 비용이 크거나 같다면 갱신을 하지 않는다.

	1	2	3	4	5
	0	--	--	--	--
1	0	5	4	--	--
2
3
4

/////////////////////

다음으로 간선을 두 번 사용할 경우,

간선을 한 번 사용했을 경우의 결과를 이용하면 된다.

먼저 정점 1부터,

정점1 -> 정점2 : +5 의 비용이 든다(0 + 5). 정점2의 현재 비용(5)와 같으므로 갱신하지 않음

정점1 -> 정점3 : +4 의 비용이 든다(0 + 4). 정점3의 현재 비용(4)와 같으므로 갱신하지 않음

다음 정점 2,

정점2 -> 정점3 : -3 의 비용이 든다(5 + -3). 정점3의 현재 비용(4)보다 2가 더 작으므로 2를 기록

   * 정점1 -> 정점2 -> 정점3 의미

정점2 -> 정점5 : +13 의 비용이 든다(5 + 13). 정점5의 현재 비용(무한대)보다 18이 더 작으므로 18을 기록

   * 정점1 -> 정점2 -> 정점5 의미

다음 정점 3,

정점3 -> 정점4 : +5 의 비용이 든다(4 + 5). 정점4의 현재 비용(무한대)보다 9가 더 작으므로 9를 기록

   * 정점1 -> 정점3 -> 정점4 의미

다음 정점 4,

정점4 -> 정점2 : +3 의 비용이 든다(-- + 3). 정점2의 현재 비용(5)보다 더 크므로 갱신하지 않음

   * 경로가 없으므로 결과가 무한대가 나옴

정점4 -> 정점5 : +7 의 비용이 든다(-- + 7). 정점5의 현재 비용(무한대)보다 더 크므로 갱신하지 않음

   * 경로가 없으므로 결과가 무한대가 나옴

	1	2	3	4	5
	0	--	--	--	--
1	0	5	4	--	--
2	0	5	2	9	18
3
4

///////////////////////

다음으로 간선을 세 번 사용할 경우,

간선을 두 번 사용했을 경우의 결과를 이용하면 된다.

먼저 정점 1부터,

정점1 -> 정점2 : +5 의 비용이 든다(0 + 5). 정점2의 현재 비용(5)와 같으므로 갱신하지 않음

정점1 -> 정점3 : +4 의 비용이 든다(0 + 4). 정점3의 현재 비용(2)보다 4가 더 크므로 갱신하지 않음

   * 사실 간선을 한 번만 사용했기 때문에 의미없는 과정이다.

다음 정점 2,

정점2 -> 정점3 : -3 의 비용이 든다(5 + -3). 정점3의 현재 비용(2)와 같으므로 갱신하지 않음

정점2 -> 정점5 : +13 의 비용이 든다(5 + 13). 정점5의 현재 비용(18)과 같으므로 갱신하지 않음

   * 이 부분도 간선을 두 번만 사용했기 때문에 의미없는 과정이다.

다음 정점 3,

정점3 -> 정점4 : +5 의 비용이 든다(2 + 5). 정점4의 현재 비용(9)보다 7이 더 작으므로 7을 기록

   * 정점1 -> 정점2 -> 정점3 -> 정점4 의미

다음 정점 4,

정점4 -> 정점2 : +3 의 비용이 든다(9 + 3). 정점2의 현재 비용(5)보다 12가 더 크므로 갱신하지 않음

   * 정점1 -> 정점3 -> 정점4 -> 정점2 의미

정점4 -> 정점5 : +7 의 비용이 든다(9 + 7). 정점5의 현재 비용(18)보다 16이 작으므로 16을 기록

   * 정점1 -> 정점3 -> 정점4 -> 정점5 의미

	1	2	3	4	5
	0	--	--	--	--
1	0	5	4	--	--
2	0	5	2	9	18
3	0	5	2	7	16
4

///////////////////////

다음으로 간선을 네 번 사용할 경우(마지막 경우이다)

간선을 세 번 사용했을 경우의 결과를 이용하면 된다.

먼저 정점 1부터,

정점1 -> 정점2 : +5 의 비용이 든다(0 + 5). 정점2의 현재 비용(5)와 같으므로 갱신하지 않음

정점1 -> 정점3 : +4 의 비용이 든다(0 + 4). 정점3의 현재 비용(2)보다 4가 더 크므로 갱신하지 않음

   * 사실 간선을 한 번만 사용했기 때문에 의미없는 과정이다.

다음 정점 2,

정점2 -> 정점3 : -3 의 비용이 든다(5 + -3). 정점3의 현재 비용(2)와 같으므로 갱신하지 않음

정점2 -> 정점5 : +13 의 비용이 든다(5 + 13). 정점5의 현재 비용(16)보다 18이 더 크므로 갱신하지 않음

   * 이 부분도 간선을 두 번만 사용했기 때문에 의미없는 과정이다.

다음 정점 3,

정점3 -> 정점4 : +5 의 비용이 든다(2 + 5). 정점4의 현재 비용(7)과 같으므로 갱신하지 않음

   * 이 부분도 간선을 세 번만 사용했기 때문에 의미없는 과정이다.

다음 정점 4,

정점4 -> 정점2 : +3 의 비용이 든다(7 + 3). 정점2의 현재 비용(5)보다 10이 더 크므로 갱신하지 않음

   * 정점1 -> 정점2 -> 정점3 -> 정점4 -> 정점2 의미

정점4 -> 정점5 : +7 의 비용이 든다(7 + 7). 정점5의 현재 비용(16)보다 14가 더 작으므로 14를 기록

   * 정점1 -> 정점2 -> 정점3 -> 정점4 -> 정점5 의미

	1	2	3	4	5
	0	--	--	--	--
1	0	5	4	--	--
2	0	5	2	9	18
3	0	5	2	7	16
4	0	5	2	7	14

이렇게 시작 정점1에서 도착 정점5까지의 최소 거리를 구할 수 있게 되었다.

///////////////////////

처음에 이해가 잘 안 됐었는데,

과정을 그려가면서 해보니까 이해가 되었다.

이해가 잘 안 간다면 과정을 그려보는게 도움이 많이 될 것 같다.

혹여나 나중에 까먹더라도 이 과정을 다시 따라가 보면서 기억을 떠올려봐야지...

이제 코드 분석도 해보자!

#. Code

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
int dist[101];
 
struct Edge {
    int s;
    int e;
    int val;
    Edge(int a, int b, int c) {
        s = a;
        e = b;
        val = c;
    }
};
 
int main() {
    freopen("input.txt", "rt", stdin);
    vector<Edge> Ed;
    int i, n, m, a, b, c, j;
 
    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        Ed.push_back(Edge(a, b, c));
    }
 
    for (i = 1; i <= n; i++) {
        dist[i] = 2147000000;
    }
 
    dist[1] = 0;
    for (i = 1; i < n; i++) {
        for (j = 0; j < Ed.size(); j++) {
            int s = Ed[j].s;
            int e = Ed[j].e;
            int w = Ed[j].val;
            if (dist[s] != 2147000000 && dist[s] + w < dist[e]) {
                dist[e] = dist[s] + w;
            }
        }
    }
 
    for (j = 0; j < Ed.size(); j++) {
        int u = Ed[j].s;
        int v = Ed[j].e;
        int w = Ed[j].val;
        if (dist[u] != 2147000000 && dist[u] + w < dist[v]) {
            printf("-1\n");
            exit(0);
        }
    }
    printf("%d\n", dist[n]);
 
    return 0;
}

line 9~18) 시작 정점, 도착 정점, 가중치를 저장하는 구조체 생성

line 26~29) 구조체를 저장하는 벡터에 입력된 시작, 종료 정점과 가중치를 push

line 31~33) 초기 거리를 max로 초기화

line 35) 시작 정점은 거리 비용을 0으로 초기화

line 36~45) 간선을 한 개부터 n-1개까지 사용해보아야 하므로 1부터 n-1 까지 반복

line 37~44) 저장된 가중치 정보 개수만큼 반복

line 38~40) 시작 정점, 도착 정점, 가중치 정보를 변수에 저장

line 41~43) 시작 정점이 무한대가 아니고, 시작정점의 거리 비용에 도착정점까지의 가중치를 더한 결과가 

               도착정점까지의 가중치보다 작다면, 해당 도착정점의 거리 비용을 갱신

line 47~55) 간선을 정점개수만큼 사용해서 최소 비용이 나온다면, 음의 사이클이 존재하는 것이므로 "-1"을 출력

#. Result

  - Input --------------------------------------------------------

5 7 

1 2 5 

1 3 4 

2 3 -3 

2 5 13 

3 4 5 

4 2 3 

4 5 7 

1 5

------------------------------------------------------------------

  - Output --------------------------------------------------------

14

------------------------------------------------------------------