다익스트라 알고리즘
길 찾기 앱은 집 문 앞에서 거의 어디로든 가는 가장 빠른 길을 압니다. 그 아이디어의 중심에는 Edsger Dijkstra가 1956년에 20분쯤 만에 생각해 낸 알고리즘이 있습니다. 시작점에서 바깥으로 퍼져 나가며, 항상 가장 가까운 곳부터 끝내는 것입니다.
아이디어
길이가 서로 다른 도로로 연결된 도시들을 떠올려 보세요. 질문은 이렇습니다. 우리 도시에서 다른 모든 도시까지 가는 가장 짧은 길은 무엇일까? 모든 도로를 똑같이 친다면 너비 우선 탐색으로 답할 수 있지만, 여기서는 도로를 더 많이 지나는 경로가 더 짧을 수도 있습니다. 다익스트라 알고리즘은 도시마다 지금까지 찾은 최단 거리를 기억하고, 거리가 확실한 도시들의 영역을 넓혀 갑니다. 이때 항상 아직 확실하지 않은 가장 가까운 도시를 더합니다.
단계별 설명
시작 노드의 거리를 0, 다른 모든 노드를 무한대로 둡니다. 시작 노드를 우선순위 큐에 넣습니다. 우선순위 큐는 항상 거리가 가장 작은 노드를 내주는 큐입니다. 그 노드를 꺼내면 거리가 확정됩니다. 확정되지 않은 이웃 노드마다 이 노드를 거치는 거리, 즉 이 노드의 거리에 간선 길이를 더한 값을 계산합니다. 그 값이 이웃 노드의 지금까지 거리보다 짧으면 거리를 낮추고, 이 노드를 그곳으로 가는 길로 기억하고, 이웃 노드를 큐에 넣습니다. 이것을 간선 완화라고 합니다. 큐가 빌 때까지, 또는 목표를 꺼낼 때까지 반복합니다.
예제
간선 A–B의 길이가 4, A–C가 1, B–C가 2, B–D가 1, C–D가 5, D–E가 3이고, A에서 시작한다고 합시다. A를 꺼내면 B는 거리 4, C는 거리 1을 얻습니다. C가 가장 가까우므로 1로 확정되고, C를 거치면 B는 1 + 2 = 3으로 줄고 D는 1 + 5 = 6을 얻습니다. 이제 B가 가장 가까워 3으로 확정되고, B를 거치면 D는 3 + 1 = 4로 줄어듭니다. D는 4로 확정되고 E에 4 + 3 = 7을 줍니다. 따라서 A에서 E까지 가장 짧은 길은 길이 7인 A → C → B → D → E입니다. A → B → D → E는 간선이 더 적지만 길이가 8입니다.
왜 올바른가
노드 X가 큐에서 가장 가깝고 거리가 d라고 합시다. 시작 노드에서 X로 가는 다른 모든 길은 어딘가에서 확정된 노드의 영역을 벗어나야 하고, 그 영역 밖에서 처음 닿는 노드는 큐에 있으므로 이미 d 이상 떨어져 있습니다. 음수 간선이 없으므로 나머지 길이 그것을 더 짧게 만들 수 없습니다. 따라서 d가 X까지의 최단 거리입니다. 음수 간선이 있으면 이 논증이 깨지므로, 모든 간선을 계속 반복해서 완화하는 벨만-포드 알고리즘을 대신 씁니다.
역사와 활용
Edsger W. Dijkstra는 1956년 암스테르담의 새 컴퓨터 ARMAC을 선보이기 위해 네덜란드 도시 사이의 경로를 찾는 이 알고리즘을 고안했고, 1959년에 발표했습니다. 같은 아이디어가 더 똑똑한 큐와 함께 길 찾기 앱과 OSPF, IS-IS 같은 인터넷 라우팅 프로토콜에서 돌아갑니다. 이 프로토콜들은 데이터가 라우터 사이를 오가는 가장 짧은 길을 계산합니다. A* 탐색은 남은 거리의 추정치를 더하므로 목표 쪽으로 향하며 더 적은 노드를 봅니다.
직접 해 보기
앱을 열고 단계를 누르세요. 간선의 숫자는 그 길이이고, 각 노드의 숫자는 지금까지의 거리입니다. 큐에 있는 노드는 파란색, 확정된 노드는 초록색이며, 그래프 아래의 큐는 가까운 순서로 노드와 거리를 보여 줍니다. 더 길어 보이는 경로가 사실은 더 짧아서 거리가 줄어드는 순간을 지켜보고, 목표를 골라 목표가 확정되자마자 탐색이 멈추는 것을 확인하세요.
자주 묻는 질문
다익스트라 알고리즘의 시간 복잡도는?
우선순위 큐에 따라 다릅니다. 단순한 목록을 쓰면 노드 V개에 대해 O(V²), 이진 힙을 쓰면 간선 E개에 대해 O((V + E) log V), 피보나치 힙을 쓰면 O(E + V log V)입니다. 마지막은 1984년 Michael Fredman과 Robert Tarjan이 보였습니다.
다익스트라 알고리즘은 음수 간선 가중치를 처리할 수 있나요?
아니요. 노드가 큐에서 가장 가까워지면 그 거리가 더 나아질 수 없다고 가정하는데, 음수 간선은 이를 깰 수 있습니다. 음수 간선이 있는 그래프에는 벨만-포드 알고리즘을 쓰세요.
다익스트라 알고리즘은 모든 노드까지의 경로를 찾나요?
네. 끝까지 실행하면 시작 노드에서 도달할 수 있는 모든 노드까지의 최단 거리를 주고, 기억한 노드들이 최단 경로 트리를 이룹니다. 경로가 하나만 필요하면 목표가 확정될 때 일찍 멈춰 작업을 아낄 수 있습니다.
다익스트라 알고리즘과 A*는 어떤 관계인가요?
A* 탐색은 힌트를 더한 다익스트라 알고리즘입니다. 지금까지의 거리에 지도 위의 직선거리 같은 남은 거리의 추정치를 더해 큐의 순서를 정합니다. 추정이 좋으면 훨씬 적은 노드만 보고도 같은 최단 경로를 찾습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
다익스트라 알고리즘 해 보기