[ 벨만포드 알고리즘 ] 개념과 구현방법 (C++)

이번 글에서는 벨만포드 알고리즘에 대해서 알아보자.

 

1. 벨만포드 알고리즘 ??

그래프 알고리즘에서 '최소비용'을 구하는 대표적인 알고리즘으로는 '다익스트라 알고리즘', '벨만포드 알고리즘', '플로이드

워샬 알고리즘' 등이 있다. 벨만포드 알고리즘도 그래프에서 최소비용을 구할 수 있는 알고리즘 중에 하나이다.

그럼 다익스트라 알고리즘과의 차이는 ? 플로이드 워샬 알고리즘과의 차이는 ? 언제 벨만포드를 써야하는데 ? 와 같은 궁금증들은 차근차근 알아가보도록 하자.

벨만포드 알고리즘은 최소비용을 구하는 알고리즘 중에서도, 한 정점에서 다른 모든 정점으로 가는데 걸리는 최소비용을

구하는데 사용하는 알고리즘이다. 이 점은 다익스트라와 동일하다.

그런데 언제 벨만포드를 쓰고 언제 다익스트라를 사용할까 ?? 그리고 밑에서 이야기 하겠지만, 벨만포드 알고리즘은 일반적으로 다익스트라 알고리즘보다 더 시간이 오래 걸리는 탐색 방법인데 굳이 이 방법을 써야할까 ?? 다익스트라를 남겨두고 ??

이런 부분에 대해서 밑에서 알아보도록 하자.

이번 글에서는 벨만포드 알고리즘을 설명하는 과정에서 다익스트라 알고리즘과의 차별화된 점에 대해서 이야기하는 부분이

있을 수 있으므로, 아직 다익스트라 알고리즘에 대해서 잘 모르시는 분들은 아래의 글을 읽고 오는 것을 권장드립니다.

[ 다익스트라 알고리즘 알아보기(Click) ]

 

2. 벨만포드 알고리즘의 동작 원리

벨만포드 알고리즘은 '모든 경우의 수를 다 탐색해 가면서 최소비용'을 찾게 된다.

다익스트라 알고리즘과는 달리 그리디 하지 않게 동작한다. 다익스트라 알고리즘은 "지금 당장 눈앞에 보이는, 연결되어 있는

정점들 중에서 최소비용으로 연결된 정점을 선택" 하는 방식, 즉, 그리디스럽게 접근했다면 벨만포드 알고리즘은 그리디 하지 않고, 모든 경우의 수를 탐색하는 동작 원리를 가지고 있다.

벨만포드 알고리즘의 동작원리는 다음과 같다.

1. 모든 간선들을 탐색하면서, 간선이 잇는 출발정점이 '한번이라도 계산 된 정점' 이라면 해당 간선이 잇는 정점의

  거리를 비교해서 업데이트 한다.

2. 1번 과정을 반복한다.

과정을 이렇게 말로 표현하니 너무나도 간단해보인다. 먼저 2번 과정에서 '반복한다' 라고 말을 했는데, 몇 번을 반복하는지

부터 알아보자. 간단하게 말해서 벨만포드 알고리즘은 "모든 간선들이 모든 정점들을 최단거리로 이을 수 있을 만큼, 계속해서

반복" 하면서 거리를 갱신해나가는 방식이다.

그렇다면, 모든 정점들을 다 잇기 위해서는 최소 몇번을 탐색해야 할까 ?? 아래의 그림을 한번 봐보자.

 

위와 같은 그래프가 있을 때, 모든 간선을 통해서 모든 정점들을 이을려면 몇 번 반복해야할까 ??

물론, 위에서 말한 '한번이라도 계산된 정점' 이라는 말(아직 구체적인 의미를 몰라도 괜찮다) 때문에 1번 정점을 시작점으로

잡고, 1번 정점을 거리가 0이라고 계산했다고 가정해보자.

그럼, 1 → 2 를 잇는 간선에 의해서 2번 정점이 계산될 것이고 (2번 정점 계산됨)

그 이후, 2 → 3을 잇는 간선에 의해서 3번 정점이 계산될 것이고 (3번 정점 계산됨)

그 이후, 3 → 4를 잇는 간선에 의해서 4번 정점이 계산될 것이다. (4번 정점 계산됨)

총 3번 반복했더니, 모든 정점의 거리를 구할 수 있었다.

즉 ! 정점의 총 갯수를 N 개라고 가정한다면, 위에서 말한 '1번과정'을 총 N - 1번 반복하면 된다.

그럼 ! 지금부터 그림을 통해서 1번과정을 구체적으로 알아보도록 하자.

 

이와 같은 그래프가 있다. 초기의 최소비용을 저장하는 배열인 int Dist[] 배열의 초기값은 모두 무한대(INF) 일 것이다.

이렇게 세팅되어 있는 상태일 것이다.

1. 모든 간선들을 탐색하면서, 간선이 잇는 출발정점이 '한번이라도 계산 된 정점' 이라면 해당 간선이 잇는 정점의

  거리를 비교해서 업데이트 한다.

이 말을 그대로 하면 진행해보자. 하지만 진행하기에 앞서, 위와 같은 상태에서 진행을 한다면 아무런 정점도 업데이트가

되지 않을 것이다. 왜냐하면 ? '한번이라도 계산 된 정점' 이 없기 때문이다. 따라서, 가장 무난하게 1번 정점을 시작점이라

생각하고, 1번 정점까지의 거리 = 0 이라고 계산을 했다고 가정 한 후에 진행을 해보자.

간선들의 상태를 먼저 간단하게 적어보자면 다음과 같이 세팅되어 있을 것이다. 보다 수월한 설명을 위해 간선에 이름을

알파벳으로 적어보았다. 큰 의미는 없다.

그럼 이 상태에서 모든 간선들을 탐색해보자. 절대로 뒤에 주어진 조건인 '한번이라도 계산된 정점' 이 출발점인

간선에 한해서만 계산을 해 주어야 한다. 왜 그런지는 밑에서 알아보도록 하자.

또한, "한번이라도 계산된 정점" 이라는 말은, Dist의 값이 무한대가 아닌 정점이라는 말이다.

Dist의 초기 값이 무한대인데, 아직 한번도 계산을 진행하지 않았다면 그대로 무한대일 것이고, 한 번이라도 계산된 정점

이라면 무한대 보다는 작을 것이기 때문이다.

지금까지 '한번이라도 계산된 정점' 은 1번정점 1개가 존재한다.

그럼 이제부터 모든 간선들을 탐색해보자. 이해를 편하게 하기 위해서 모든 간선을 순차적으로 탐색하는데, 이 순서는

A ~ F 순서대로 탐색한다고 가정해보자.

 

★ 간선 'A'는 1 → 2 로 가는 비용이 '3'이 드는 간선인데, 기존의 정점'2'의 비용은 무한대 이기 때문에, 정점2의 비용이

   3으로 업데이트 될 것이다. 이 순간 ! 정점2는 '이미 한번이라도 계산된 정점' 이 된다.

★ 간선 'B'는 1 → 3 으로 가는 비용이 '2'가 드는 간선인데, 기존의 정점'3'의 비용은 무한대 이기 때문에, 정점 3의 비용이

   '2'로 업데이트 될 것이다. 이 순간 ! 정점 3은 '이미 한번이라도 계산된 정점'이 된다.

★ 간선 'C'는 1 → 4로 가는 비용이 '5'가 드는 간선이다. '1'은 이미 한번이라도 계산된 정점이므로 이 간선에 의해서

   업데이트가 발생할 수 있고, 정점 '4'로 가는데 드는 비용이 5로 업데이트가 될 것이다.

★ 간선 'D'는 2 → 3 으로 가는 비용이 '3'이 드는 간선이다. 정점 '2'는 이미 한번이라도 계산된 정점이기 때문에(A 간선에

   의해서 계산이 한번 되었음) 이 간선에 의해서 업데이트 되는 비용이 있는지 확인해보자.

   2 → 3 으로 가는데 비용이 '3'이 들게 되고, 현재 정점 '3'의 비용은 '2' 이다. 그럼 값을 비교해보자.

   1 → 2 로 가는데 비용이 '3'이 들었고, 2 → 3 으로 가는데 비용이 '2' 가 들게 되므로, 총 '5'의 비용이 발생한다.  

   하지만 정점 '3'의 현재까지의 최소비용은 '2' 이기 때문에 5 > 2 이므로, 업데이트가 발생하지 않는다.

★ 간선 'E'는 3 → 4로 가는데 비용이 -4 가 드는 간선이다. 현재 정점 '4'의 최소비용은 '5'이다.

   그럼 계산을 해보면 1 → 3 으로 가는데 비용이 '2' , 3 → 4 로 가는데 비용이 -4, 더해보면 2 - 4 = -2 로 현재까지의 정점

   '4'의 최소비용인 5보다 더 작은 값이 된다. 따라서 정점'4'의 비용에 업데이트가 발생한다.

★ 간선 'F'는 4 → 2로 가는 비용이 -4가 드는 간선이다. 현재 정점 '2'의 최소비용은 '3'이다.

   그럼 1 → 4로 가는데 현재까지의 최소비용은 '-2' 이고, 4 → 2 로 가는데 드는 비용이 -4 이므로, 총 -6의 비용이 발생한다.

   현재까지의 정점'2'의 최소비용인 '3'보다 더 작은 값이므로 업데이트가 발생한다.

이렇게 탐색을 한번 하고 나면 아마 정점들의 최소비용이 다음과 같이 업데이트 되어 있을 것이다.

그림을 보면 알겠지만, 뭔가 정점까지 가는데 드는 비용의 값이 약간 이상하다는 것을 느낄 수 있다.

그래도 뭐, 일단 N - 1번 탐색은 해보라고 했고 아직 한번밖에 안해봤으니 한번 더 해보자.

지금부터는 조~~금만 간단하게 적어보겠다. 이미 모든 정점이 한번 이상 업데이트 된 정점이므로, 모든 간선에 의해서

업데이트가 일어날 수도 일어나지 않을 수도 있다.

★ 'A'간선에 의해서 업데이트가 발생하지 않는다. -6 < 3 이므로.

★ 'B'간선에 의해서 업데이트가 발생하지 않는다. 2 = 2 이므로.

★ 'C'간선에 의해서 업데이트가 발생하지 않는다. -2 < 5 이므로.

★ 'D'간선에 의해서 업데이트가 발생한다. 'D'는 2 → 3 을 이어주는 비용이 '3'이 드는 간선이다.

   그런데 ! 현재까지 정점 '2'에 드는 최소비용은 -6이다. 그럼 1 → 2 로 가는데 드는 비용이 -6 이라는 이야기이고,

   'D'간선으로 3번 정점으로 오게 되면 -6 + 3 = -3 이 된다. 기존의 3번 정점의 최소비용인 '2'보다 더 작은 비용이기 때문에

   정점'3'에 가는 최소비용이 '-3' 으로 업데이트가 된다.

★ 'E'간선에 의해서 업데이트가 발생한다. 'E'는 3 → 4 를 이어주는 비용이 '-4'가 드는 간선이다.

   그런데 ! 현재까지 정점 '4'에 드는 최소비용은 -2 이다. 그럼 1 → 3 으로 가는데 비용이 현재 '-3'이 발생하고,

   3 → 4로 가는 'E'간선에 의해서 '-4'가 발생하게 되면 -7로 -2보다 더 작은 비용이 들게된다.

   따라서 정점 '4'의 최소비용이 '-7'로 업데이트 된다.

★ 'F'간선에 의해서 업데이트가 발생한다. 'F'는 4 → 2 를 이어주는 비용이 '-4'가 드는 간선이다.

   그런데 ! 현재까지 정점 '2'에 드는 최소비용은 -6 이다. 그럼 1 → 4 로 가는데 비용이 '-7'이 들게 되고,

   4 → 2 로 가는 'F'간선에 의해서 비용이 '-4'가 발생하게 되면, '-11'로 -6보다 더 작은 비용이 들게된다.

   따라서 정점 '2'의 최소비용이 '-11'로 업데이트 된다.

이렇게 전체간선을 탐색하는 과정을 총 2번 진행해보았다. 지금까지 정점까지 가는데 드는 최소비용을 정리해보면 다음과 같다.

 

위에서 총 N - 1번을 탐색해봐야 한다고 했으므로, 한번을 더 해봐야 하지만(실제로 코드에서는 한번 더 진행함) 이 글에서

더 이상은 탐색해보지 않겠다.

그럼 지금부터 이상하다고 생각한 것들, 정확한 이유를 모르고 일단 하라고 해서 했던 내용들에 대해서 알아보자.

가장 먼저 탐색하기에 앞서서 모든 간선을 탐색할 때, "해당 간선의 출발지점이 이미 한번이라도 계산된 정점일 때만,

해당 간선에 의한 업데이트를 진행" 했다. 왜 출발지점이 한번이라도 계산된 정점일 때만 업데이트를 진행했는지

알아보자.

먼저 위에서도 말했듯이, 벨만포드 알고리즘은 "한 정점에서 다른 모든 정점까지의 최소비용을 구하는 알고리즘" 이다.

우리는 이 '한 정점'을 가장 무난하게 '1'번 정점으로 생각하고 거리를 구한 것이다.

그럼 아래의 상황을 한번 봐보자.

위의 그래프에서 약간 상태를 바꿔보았다.

지금부터 위에서 했던 탐색을 다시한번 해보자. 물론 굉장히 간략하게만 적어보겠다.

★ 1번 정점을 한번이라도 방문한 정점이라 표시하기 위해서 Dist[1] = 0 으로 설정 후 탐색시작.

★ 간선 'A'에 의해서 '2'번 정점이 '3'으로 업데이트 Dist[2] = 3 (2번 정점은 한번이라도 계산된 정점이 되었다.)

★ 간선 'B'에 의해서 '3'번 정점이 '3'으로 업데이트. Dist[3] = 3 (3번 정점은 한번이라도 계산된 정점이 되었다.)

★ 간선 'C'에 의해서 '4'번 정점이 '1'로 업데이트. Dist[4] = 2 (4번 정점은 한번이라도 계산된 정점이 되었다.)

★ 간선 'D'에 의해서 '2'번 정점이 '-2'로 업데이트. Dist[2] = -2

★ 간선 'E'에 의해서 '4'번 정점이 '1'로 업데이트. Dist[4] = 1.

위에서 빨간색으로 쓴 간선 'E'를 한번 봐보자. 눈으로 딱봐도 알겠지만, 위의 그래프에서 1번 정점에서 4번 정점으로 가는

최소 비용을 구할 때, 1 → 5 → 4 로는 계산이 불가능하다. 왜냐하면 5번 정점으로는 갈 수가 없기 때문이다.

즉, 우리가 계속 말해왔던 "해당 간선의 출발정점이 한번이라도 계산된 정점이라면 ! 업데이트를 해라" 라는 이유가

여기에 있다.

5번 정점은 실제로 한번도 업데이트 되지 않은 정점이다. 즉, Dist의 값이 무한대일 것이다. 하지만, 위에서 말한 규칙을

무시해버리고, 단순히 거리가 더 짧다는 이유만으로 업데이트를 해버린다면 ?

위와 같이 1번 정점에서 4번정점으로 가는 최단거리가 '1'이다. 라는 뭔가 이상한 결과가 나와버린다.

이러한 이유 때문에 "해당 간선의 출발정점이 한번이라도 계산도니 정점일 때만" 업데이트를 해야 하는 것이다.

 

그 다음 궁금증으로 넘어가보자.

이 글을 읽는 내내 본인이 만든 그래프 자체가 굉장히 이상하다고 느꼈을 것이다. 가중치에 음수값이 들어있질 않나,

업데이트를 하다보니 어떤 정점으로 가는데 드는 비용이 음수가 되질 않나... 이런 부분에 대해서 이상하다고 느꼈을 것이다.

사실은, 본인이 그래프에 음수 가중치를 넣고, 비용이 음수가 발생하는 상황을 일부러 조작해서 만든 그래프이다.

왜냐하면 이게 '벨만포드 알고리즘을 사용하는 이유' 이기 때문이다.

잠깐만 다익스트라 알고리즘 이야기로 넘어가보자. 다익스트라 알고리즘을 사용할 때는 '음의 가중치가 있는 순간, 다익스트라의 규칙이 깨져버리기 때문에, 오로지 양의 가중치만 있을 때 사용이 가능한 알고리즘' 이라고 말을 했었다.

즉, 위의 그래프 같은 경우 다익스트라 알고리즘을 사용할 수가 없다. 왜 ?? 음의 가중치가 존재하기 때문이다.

그런데 벨만포드 알고리즘은 위의 상황에서 '음의 사이클'이 있다라는 것을 판단할 수가 있다.

 

위의 그래프를 다시한번 가져와봤다. 우리는 한번의 탐색 그리고 2번의 탐색을 하고나니 해당 정점들까지 가는데 드는 비용이

음수가 발생했다. 그리고 원래는 한번 더 탐색을 해야하지만, 하지 않겠다고 말을 하고 탐색을 끝내버렸다.

그렇다면 한번 더 진행했다면 어떤 결과가 나왔을까 ??

이게 우리가 모든 간선을 2번 탐색하고 나서의 '1번 정점에서 각 정점까지 가는데 드는 최소비용' 이였다.

여기서 한번 더 진행하면 어떻게 될까?? 모두들 직접 해보면 좋겠지만, 본인이 해보니 다음과 같이 나왔다.

이게 우리가 정상적으로 탐색을 N - 1번 진행했을 때 얻을 수 있는 결과이다.

그럼 "1번 정점에서 2번 정점으로 가는데 드는 최소비용이 얼마야?" 라고 물으면 뭐라고 답할 수 있을까 ??

과연, "-16이 2번 정점으로 가는데 드는 최소비용이다 !" 라고 말을 할 수 있을까 ??

말을 못한다. 왜 ? 지금 3번 업데이트를 진행했을 때, '2'번으로 가는 최소비용이 -16일 뿐이지, 만약에 최소비용을

구하기 위해서 2 → 3 → 4 → 2 를 계속해서 왔다갔다 해버리면 '2'번정점으로 가는 최소비용이

-16 , -21, -26, -31, -36 ... 으로 한없이 작아진다는 것을 알 수 있다.

이와같이, 음의 가중치 때문에 최소비용이 제대로 계산되지 않고, 탐색을 하면 할수록 그 비용을 무한대에 가까이 작게

만들 수 있는 이런 아이러니한 상황을 "음의 사이클" 혹은 "음수 사이클" 이라고 말을 한다.

그럼 벨만포드 알고리즘은 이런 상황에서 최소비용을 구할 수 있어서 사용하는 알고리즘인가 ??

이 상황에서 최소비용을 구할 수 있는 알고리즘이 벨만포드 알고리즘이 아니라, 위의 상황이 "음의 사이클이 발생해서,

최소비용을 제대로 계산할 수 없다" 라고 알 수 있게 만들어주는 알고리즘이다.

그럼 음의 사이클이 발생하는지 어떻게 알까 ??

우리는 지금까지 N - 1번동안 모든 간선들에 대해서 가중치를 업데이트 해 왔다.

왜냐하면, N - 1번 탐색을 하게되면 모든 정점에 들어가는 최소비용을 구할 수 있기 때문이였다.

그런데 이 만큼 탐색을 하고, 딱 한번만 더 탐색을 해보는 것이다. 정상적이였다면, 더 이상의 비용이 업데이트 되지 않을 것이다. 그럼 ! 정상적인 상황을 그림으로 한번 봐보자. 빠르게 위에서 말했던 과정을 진행해보자.

★ 1번 정점을 이미 한번이라도 계산된 정점을 만들어 주기 위해서 Dist[1] = 0 으로 설정.

★ 간선 'A'에 의해서 '2'번 정점의 비용이 '3'으로 업데이트. (2번은 한번이라도 계산된 정점)

★ 간선 'B'에 의해서 '3'번 정점의 비용이 '3'으로 업데이트. (3번은 한번이라도 계산된 정점)

★ 간선 'C'에 의해서 업데이트가 발생하지 않는다.

★ 간선 'D'에 의해서 '4'번 정점의 비용이 '2'(3 - 1)로 업데이트. (4번은 한번이라도 계산된 정점)

★ 간선 'E'에 의해서 업데이트가 발생하지 않는다. 4번 정점으로 가는데 드는 비용은 '2' 이고, 4 → 2로 가는 간선 'E'에 의해서

   계산을 하더라도, 2 + 1 = 3 으로 기존의 정점 '2'의 비용인 3과 동일하기 때문에 업데이트 되지 않는다.

이렇게 한번 계산을 했다. 우리는 총 N - 1번, 즉 3번 계산을 해야 하므로 2번 더해보자.

★ 'A'에 의해서 업데이트 발생하지 않음.

★ 'B'에 의해서 업데이트 발생하지 않음.

★ 'C'에 의해서 업데이트 발생하지 않음.

★ 'D'에 의해서 업데이트 발생하지 않음.

★ 'E'에 의해서 업데이트 발생하지 않음.

이렇게 한번 더 해봤는데, 한번 더 하더라도 위와 결과가 동일하게 발생한다.

사실, 위의 그래프가 굉장히 지금 상황을 설명하기 별로인 것 같지만, 하고자 했던 말은 이것이다.

"정상적인 그래프라면, 즉, 음의 사이클이 발생하지 않는 그래프라면, N - 1번을 탐색한 이후에, 또 한번의 탐색을 더 하더라도 절대로 ! 최소비용이 변하는 정점이 발생하지 않는다" 라는 것이다.

위의 그래프가 별로라고 했던 것은, 1번만 탐색을 했는데도 더 이상 최소 비용이 변하지 않는 그래프라서 별로라고 한 것이다.

그럼 본론으로 다시 돌아와서, 벨만포드 알고리즘에서 '음의 사이클'이 존재한다는 것을 어떻게 판단할까 ??

바로, "N - 1번 모든 간선을 탐색 후, 한번 더 모든 간선을 탐색" 을 진행하면 된다.

그렇게 한다면 ?? '음의 사이클'을 가진 그래프였다면, 이 '한번 더 탐색'하는 과정에서 최소비용이 변하는 정점이 있을 것이다.

위에서 봤듯이, '2'번 정점이 탐색을 하면 할수록 계속해서 최소비용이 바뀐 것과 같이 !

따라서, 벨만포드 알고리즘은 이렇게 음의 가중치가 존재할 때, '음의 사이클'이 존재하는지 안하는지까지 파악할 수 있는

알고리즘이다.

다익스트라 알고리즘에 비해서 최소 비용을 찾는 시간이 일반적으로 더 오래 걸리는 알고리즘이지만, 이러한 부분 때문에

다익스트라 알고리즘에서는 할 수 없었던 경우를 벨만포드 알고리즘으로는 해결할 수 있고, 벨만포드 알고리즘을 사용하는

것이다.

 

3. 벨만포드 알고리즘 구현하기

 

void Bellman_Ford()
{
    Dist[1] = 0;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < Edge.size(); j++)
        {
            int From = Edge[j].first.first;
            int To = Edge[j].first.second;
            int Cost = Edge[j].second;
 
            if (Dist[From] == INF) continue;
            if (Dist[To] > Dist[From] + Cost) Dist[To] = Dist[From] + Cost;
        }
    }
 
    for (int i = 0; i < Edge.size(); i++)
    {
        int From = Edge[i].first.first;
        int To = Edge[i].first.second;
        int Cost = Edge[i].second;
 
        if (Dist[From] == INF) continue;
        if (Dist[To] > Dist[From] + Cost)
        {
            cout << "음의 사이클이 존재하는 그래프입니다." << endl;
            return;
        }
    }
    cout << "음의 사이클이 존재하지 않는, 정상적인 그래프 입니다." << endl;
}

위의 코드가 벨만 포드를 구현한 코드이다.

Dist배열의 초기상태는 모두 'INF(무한대)' 로 초기화 되어 있는 상태이다.

그리고, 'Edge'는 간선의 정보를 저장한 vector인데, Edge에는 { 시작점, 도착점, 비용 } 이 저장되어 있다.

라인별로 어떤 역할을 하는지 알아보자.

line3)

- 가장 처음에 '1'번 정점을 "이미 한번이라도 계산된 정점" 이라고 표시해주기 위해서 1번정점의 Dist값을 0으로 바꿔주는

  부분이다. 이 부분이 없다면, 모든 간선을 탐색하는 부분에서, "이미 한번이라도 계산된 정점"이 하나도 없기 때문에

  어떠한 값도 계산이 되지 않는 문제가 발생한다.

line4 ~ 15)

- line4)를 보면 1 ~ N - 1 까지, 총 N - 1번 반복한다는 것을 알 수 있다.

  위에서도 말했듯이, "모든 정점을 가는데 드는 최소비용을 알기 위해서는 최소 'N - 1'번 탐색"을 해봐야 하기 때문이다.

- line6 ~ 13)을 보면, 모든 간선을 탐색하면서, 정점에 드는 최소비용을 업데이트 하는 과정인데, line12 에 주목하자.

  바로 "이미 한번이라도 계산된 정점" 인지 아닌지 판단하는 부분이다.

  이미 한번이라도 계산된 정점 이라면 Dist의 값이 무한대가 아닐 것이다.

line17 ~ 29)

- 그래프가 '음의 사이클'을 갖는지 판단하기 위해서, N - 1번 탐색 후 ! 한번 더 모든 간선들을 탐색하는 부분이다.

  정상적인 그래프라면 저 과정에서 더 이상 최소비용이 업데이트 되는 정점은 없을 것이다.

  하지만, 음의 사이클을 갖는 그래프라면, 최소비용이 업데이트 되는 정점이 발생할 것이다. 따라서 그런 경우

  line26)에서 출력 후 바로 return을 시켜주는 부분이다.

 

위와 같이 벨만포드 알고리즘을 구현할 수 있다.

최소비용을 구하는 문제에서 상황에 따라서 사용할 수 있는 알고리즘이니 알아두면 좋은 알고리즘인 것 같다 !!