최단 경로(Shortest Path)는 그래프의 종류에 따라 그 진의가 다르게 해석될 수도 있는 주제입니다. 가중치가 없는 그래프에서는 간선 개수가 가장 적은 경로가 최단 경로이지만 가중치가 있는 그래프에서는 일반적으로 시작 노드에서 끝 노드까지 이동할 때 거치는 간선의 가중치의 총합이 최소가 되는 것을 말합니다. 이를테면 다음 그래프는 간선에 가중치가 있으므로 최단 경로의 기준은 간선의 가중치의 총합입니다.
노드 1에서 5까지의 최단 경로를 구한다고 했을 때, 간선 개수를 기준으로 하면 1 → 5는 간선의 개수가 1개로 가장 적으니 이것이 최단 경로가 됩니다. 하지만 가중치의 합을 기준으로 하면 1 → 5는 가중치가 49이고, 1 → 2 → 5는 가중치가 24이므로 이것이 최단 경로가 됩니다. 여기서는 최단 경로를 구하는 대표적인 알고리즘인 다익스트라 알고리즘, 벨만-포드 알고리즘을 차례로 알아보겠습니다.
1편은 다익스트라 알고리즘입니다.
다익스트라 알고리즘
다익스트라(Dijkstra) 알고리즘은 1959년 에츠허르 데이크스트라(Edsger Wybe Dijkstra)가 발표한 최단 경로를 구하는 알고리즘입니다. 가중치가 있는 그래프의 최단 경로를 구하는 문제는 대부분 다익스트라 알고리즘을 사용한다고 보면 될 정도로 중요한 알고리즘입니다(또는 데이크스트라 알고리즘이라고도 합니다). 다익스트라 알고리즘은 다음과 같은 과정으로 동작합니다.
※ 다익스트라 알고리즘을 고안한 에츠허르 데이크스트라는 네덜란드 사람입니다. 네덜란드 발음으로 dijkstra는 데이크스트라가 맞지만 우리나라에서는 다익스트라라고 부르는 경우가 많으므로 이 책도 다익스트라라고 하겠습니다.
- 시작 노드를 설정하고 시작 노드로부터 특정 노드까지의 최소 비용을 저장할 공간과 직전 노드를 저장할 공간을 마련합니다.1-1 최소 비용을 저장할 공간은 모두 매우 큰 값으로 초기화합니다. 여기서는 무한대(Infinite)를 의미하는 약자 INF로 표현하겠습니다. 직전 노드를 저장할 공간도 INF로 초기화합니다.1-2 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 합니다.
- 해당 노드를 통해 방문할 수 있는 노드 중, 즉 아직 방문하지 않은 노드 중 현재까지 구한 최소 비용이 가장 적은 노드를 선택합니다.2-1 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소 비용으로 갱신합니다.2-2 이때 직전 노드도 같이 갱신합니다.
- 노드 개수에서 1을 뺀 만큼 반복합니다.
글로만 보면 난해하게 느껴질 수 있습니다. 다익스트라 알고리즘의 동작을 그림과 함께 차분하게 알아봅시다.
01단계 시작 노드 A의 최소 비용은 0, 직전 노드는 A로 초기화합니다.
02단계 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 A를 선택합니다. 이후 해당 노드를 거쳐서 각 노드까지 가는 비용과 기존에 구한 각 노드의 최소 비용을 비교합니다. 노드 A에서 노드 B, C, E의 가중치는 각각 4, 4, 1입니다. 현재까지 해당 노드의 최소 비용은 모두 INF이므로 B의 최소 비용을 4, C의 최소 비용을 4, E의 최소 비용을 1로 갱신합니다. 이때 최소 비용이 갱신된 노드의 직전 노드를 A로 갱신합니다.
03단계 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 E를 선택합니다. 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인합니다. 노드 C의 현재 최소 비용은 4이고, E를 거쳤을 때의 비용은 E의 최소 비용(1)과 E → C의 가중치(2)를 합친 값 3입니다. 현재까지 구한 최소 비용보다 이 값이 더 작으므로 C의 최소 비용을 3, 직전 노드를 E로 수정합니다.
04단계 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 C를 선택합니다. 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인합니다. 노드 D의 경우 기존 최소 비용이 INF(경로가 없음)이지만, C를 거치면 C의 최소 비용(3) + C → D의 가중치(8)를 합쳐 11이 되어 더 작습니다. 최소 비용을 11로, 직전 노드를 C로 갱신합니다.
05단계 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 B를 선택합니다. 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인합니다만, 지금은 최소 비용을 갱신할 필요가 없습니다.
06단계 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 D를 방문합니다. 여기도 같은 작업을 반복합니다. 최소 비용 갱신은 하지 않습니다.
07단계 모든 곳에 방문했습니다. 각 노드까지의 최소 비용과 직전 노드를 갱신했습니다. 특정 노드로부터 직전 노드가 시작 노드가 될 때까지 거슬러 올라가면 최소 비용을 구성하는 세부 경로도 알 수 있습니다. 예를 들어 노드 C의 경우 최소 비용은 3이며, ➊ 직전 노드 E, ➋ A를 거슬러 올라가 세부 경로가 A → E → C임을 알 수 있습니다.
💡 합격 조언: “음의 가중치가 있는 그래프에서 다익스트라 알고리즘은 어떨까?”
결론부터 말하면 다익스트라 알고리즘은 양의 가중치만 있는 그래프에서만 동작하므로 음의 가중치가 있는 그래프에서 제대로 동작하지 않습니다. 다익스트라 알고리즘은 시작 노드에서 각 노드까지의 최소 비용을 갱신하는 과정을 반복하죠.
현재까지 구한 각 노드의 최소 비용 중 가장 작은 노드를 선택하여 움직입니다. 알고리즘 기법 중에 각 단계에서 가장좋은 것을 선택하는 전략을 가진 그리디 알고리즘과 원리가 같습니다. 그런데 다익스트라 알고리즘은 한 번 방문한 노드는 다시 방문하지 않습니다. 그러니 음의 가중치가 있는 그래프에서 제대로 동작하지 않는 것이죠. 이런 그림을 생각해보면 됩니다.
다익스트라 알고리즘대로라면 초기에 A → B를 8, A → C를 7로 갱신한 이후 다음 방문 위치를 갱신한 거리 중 가장 짧은 거리를 가지는 노드 C으로 정합니다. 하지만 A → B → C로 가면 5로 A에서 C까지 갈 수 있는 더 짧은 거리를 발견할 수 있습니다. 그러나 다익스트라 알고리즘은 한 번 방문한 C는 다시 방문하지 않으므로 이것을 놓칩니다.
그럼에도 다익스트라 알고리즘을 많이 사용하는 이유는 대부분의 경우 음의 가중치를 갖는 경우가 없고, 성능이 매우 뛰어나기 때문입니다.
※ 매 순간마다 좋아보이는 선택을 하는 것을 그리디(greedy)하다라고 합니다. 그리디를 우리말로 ‘탐욕’으로 번역합니다.
2편은 벨만-포드 알고리즘입니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
