최단 거리 알고리즘 - 다익스트라 알고리즘, 벨만-포드 알고리즘

이 글은 기술면접대비 CS전공 핵심요약집의 일부분인 알고리즘 부분의 내용을 가져와 작성하였습니다.
구글 도서 검색 을 통해 전체 페이지 240 중 102페이지를 미리보기 하실 수 있습니다.
개인적으로 아래 내용은 위키 백과를 함께 보시며 의사코드와 소스 코드를 참조하시길 권장 드립니다.
데이크스트라 알고리즘, 벨먼-포드 알고리즘

 

최단 거리 알고리즘

최단 거리 알고리즘은 그래프에서 정점 간 최단 거리를 구하기 위한 알고리즘으로, ‘다익스트라 알고리즘’ 과 ‘벨만-포드 알고리즘’ 그리고 ‘플로이드-워셜 알고리즘’이 여기에 속한다. ‘다익스트라 알고리즘’과 ‘벨만-포드 알고리즘’은 특정 정점에서 다른 정점들까지의 최단 거리를 구하고, ‘플루이드-워셜 알고리즘’은 모든 정점 간 최단 거리를 구한다.

다익스트라 알고리즘 (Dijkstra algorithm)

다익스트라 알고리즘은 간선의 가중치가 음수가 아닌 경우 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이다. 시작 정점을 설정하고, 방문 가능하면서 비용이 가장 적게 드는 정점에 방문해 비용을 갱신한다. 이때 각 정점의 비용에 우선순위 큐를 사용하면 시간 복잡도 면에서 효율적이다.

다익스트라 알고리즘의 작동 방식은 다음과 같다.

1. 초기 시작 정점에서 방문 가능한 정점에 대한 비용을 갱신하고 나머지 정점에 대한 비용은 무한대(INF, infinite)로 설정한다.
2. 방문하지 않은 정점 중 비용이 가장 적게 드는 정점에 방문한다. 해당 정점과 연결된 다른 정점의 비용을 갱신해야 하는지 확인한다. 만약 해당 정점을 거쳐 다른 정점에 방문할 때 기존보다 적은 비용이 든다면 비용을 갱신한다.
3. 모든 정점을 방문할 때까지 이와 같은 방식으로 정점 방문 비용을 갱신한다. 모든 정점을 방문했다면 알고리즘 수행을 종료한다.

1. S를 시작 정점으로 설정하고, 초기에 모든 정점에 도달하는 비용을 무한대로 설정한다.
2. 정점 S와 연결된 정점 A, B, C, D 까지의 비용을 갱신한다.
3. 방문하지 않은 정점 중 비용이 가장 적게 드는 정점 D를 방문한다. 정점 D와 연결된 정점 중 방문하지 않은 정점은 B, C, E가 있다. 정점 S에서 정점 D를 거쳐 정점 B를 방문하는 데 드는 비용 13은 기존 비용과 동일하므로 갱신하지 않는다. 정점 S에서 정점 D를 거쳐 정점 C를 방문하는 데 드는 비용 9는 기존 비용인 15보다 적다. 따라서 정점 C까지의 비용을 9로 갱신한다. 정점 S에서 정점 D를 거쳐 정점 E를 방문하는 데 드는 비용11은 기존 비용인 무한대보다 적다. 따라서 정점 E까지의 비용을 11로 갱신한다.
4. 방문하지 않은 정점 중 비용이 가장 적게 드는 정점 A를 방문한다. 정점 A와 연결된 정점 중 방문하지 않은 정점은 C이다. 정점 A를 거쳐 정점 C에 방문하는 경우 비용은 17이 든다. 기존 비용인 9보다 크므로 비용을 갱신하지 않는다.
5. 방문하지 않은 정점 중 비용이 가장 적게 드는 정점 C를 방문한다. 정점 C와 연결된 정점 중 방문하지 않은 정점은 B이다. 정점 C를 거쳐 B를 방문하면 비용 10이 든다. 기존 비용 13보다 적으므로 비용을 10으로 갱신한다.
6. 방문하지 않은 정점 중 비용이 가장 적게 드는 정점 B를 방문한다. 정점 B와 연결된 정점 중 방문하지 않은 정점은 E이다. 정점 B를 거쳐 정점 E를 방문하면 비용 25가 든다. 기존 비용 11보다 크므로 비용을 갱신하지 않는다.

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

벨만-포드 알고리즘은 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘으로, 간선의 가중치가 음수인 경우에도 적용할 수 있다. 하지만 음의 사이클이 있으면 최소 비용이 무한하게 줄어들어서 알고리즘을 적용할 수 없다.

그래프의 정점 수를 n이라고 할 때, 벨만-포드 알고리즘은 전체 간선을 n-1번 순회하며 최단 거리를 갱신한다. 간선 탐색을 n-1번 반복하는 이유는 최대 n-1개 간선을 이용해 특정 노드에서 다른 노드까지의 최단 경로를 생성할 수 있기 때문이다. 만약 n개 이상의 간선을 사용했을 때 최단 거리가 갱신된다면 이는 음의 사이클이 존재함을 의미한다. 하지만 음의 사이클이 존재한다면 최단 경로가 존재할 수 없으므로 모순이 발생한다. 즉, n개 이상의 간선을 사용해 최단 거리를 생성할 수 없다. 따라서 최단 거리는 n-1개 이하의 간선을 탐색해서 구할 수 있다.

그래프에서 가중치가 음수인 간선을 포함하면서 S를 시작 정점으로 다른 정점까지의 최단거리를 구하고자 한다면 가중치가 음수이므로 벨만-포드 알고리즘을 사용해야 한다. 벨만-포드 알고리즘은 (정점 개수)-1 만큼 모든 간선을 탐색해야 한다. 따라서 오른쪽 그림에 표시한 순서대로 간선을 탐색한다.

수행 과정을 단계별로 자세히 살펴보자.

1. 시작 정점은 S이므로 나머지 정점에 대한 거리는 무한대로 설정한다.
2. (첫 번째 순회) S를 시작 정점으로 간선 <S, A>, <S, B>, <A, E>, <E, C>, <C, A>, <B, D>를 탐색하면서 정점 A, B, C, D, E에 대해 각각 최단 거리를 갱신한다.
3. (첫 번째 순회) 간선 <D, A>, <D, E>를 탐색한다. 정점 A에 대한 기존 방문 비용은 1이다. 그런데 정점 D의 방문 비용이 10이므로 가중치 -4인 간선을 거쳐 정점 A에 도달할 경우 비용 6이 든다. 따라서 정점 A에 대한 비용을 갱신할 수 있다. 정점 E에 대한 기존 방문 비용은 14이다. 그러나 <D, E>를 거쳐 방문하면 18의 비용이 발생한다. 따라서 정점 E에 대한 비용은 갱신하지 않는다.
4. (두 번째 순회) S를 시작 정점으로 간선 <S, A>, <S, B>를 탐색한다. 정점 A와 정점 B에 대한 방문 비용은 동일하여 갱신하지 않는다.
5. (두 번째 순회) 간선 <A, E>, <E, C>, <C, A>를 탐색한다. 3에서 정점 A에 대한 비용을 6으로 갱신 했으므로 간선 <A, E>를 거치면 정점 E의 방문 비용은 9가 든다. 기존 비용인 14보다 적으므로 비용을 갱신한다. 정점 E의 방문 비용을 갱신했으므로 간선 <E, C>로 정점 C에 방문하면 비용은 7이 든다. 기존 비용인 12보다 적으므로 비용을 갱신한다. 간선 <C, A>로 정점 A에 방문할 경우 비용 8이 든다. 기존에 정점 A를 방문하는 비용 6보다 많으므로 갱신하지 않는다.
6. (두 번째 순회) 간선 <D, A>, <D, E> 를 탐색한다. 정점 D의 방문 비용은 10이고, 간선 <D, A>를 거쳐 정점 A를 방문하는 비용은 6이다. 기존 비용과 동일하므로 갱신이 필요없다. 간선 <D, E>를 거쳐 정점 E를 방문하는 데 드는 비용은 18이다. 정점 E에 대한 기존 비용은 9이므로 갱신하지 않는다.

벨만-포드 알고리즘은 간선 순회를 통해 정점의 방문 비용을 갱신한다. 갱신을 위한 순회는 (정점의 수) - 1만큼 반복해야 한다.