내비게이션 앱에서 목적지를 검색할 때, 단순히 '가장 빠른 길(1위)' 딱 하나만 보여주지 않고, '무료 도로 우선(2위)', '경치가 좋은 길(3위)' 등 여러 개의 대안 경로를 함께 제시해 줍니다. 컴퓨터 공학의 그래프 이론에서도 이와 마찬가지로 첫 번째 최단 경로뿐만 아니라 'K번째로 짧은 경로'를 구해야 하는 고난도 상황이 발생합니다. 일반적인 다익스트라(Dijkstra) 알고리즘은 노드 방문을 한 번으로 제한하여 1등 경로만 확정 짓고 끝나버리기 때문에 이 문제를 해결할 수 없습니다. 다익스트라의 탐욕적(Greedy) 전제를 영리하게 비틀어, 우선순위 큐(Priority Queue)의 배열을 활용해 K번째 경로까지 남김없이 긁어모으는 'K번째 최단 경로(K-th Shortest Path)' 알고리즘의 동작 원리를 낱낱이 해부해 보겠습니다.
1. 기존 다익스트라가 K번째 경로를 못 찾는 이유
전통적인 다익스트라 알고리즘은 dist[node]라는 1차원 배열을 사용하여 출발지에서 특정 노드까지의 '가장 짧은 거리' 단 하나만을 저장합니다. 한 번 최단 거리가 확정된 노드는, 이후에 다른 경로를 통해 조금 더 먼 거리로 빙글 돌아오더라도 "이미 더 짧은 길을 찾았으니 넌 필요 없어!"라며 가차 없이 폐기 처분(방문 처리 후 무시)해 버립니다. 하지만 우리가 K번째 길을 찾으려면, 1등뿐만 아니라 2등, 3등으로 도착하는 약간 비효율적인 경로의 정보들도 버리지 않고 소중하게 간직해야만 합니다.
2. 변형된 다익스트라: 1차원 배열에서 우선순위 큐 배열로
K개의 경로를 기억하기 위해 가장 먼저 해야 할 일은 거리 기록 장치를 바꾸는 것입니다. dist[node]를 단순한 정수 변수가 아니라, 내림차순으로 정렬되는 우선순위 큐(Max Heap) 구조로 뜯어고칩니다. 즉, 각 노드마다 K개의 빈자리를 가진 랭킹 보드(Top K)를 달아두는 것입니다.
2-1. K개의 랭킹 보드 갱신 시뮬레이션
출발지에서 탐색을 시작하여 어떤 노드 V에 도달하는 새로운 경로(비용 Cost)를 발견했다고 가정해 봅시다.
- 랭킹 보드에 빈자리가 있을 때 (기록된 경로가 K개 미만):
묻지도 따지지도 않고 이 새로운Cost를 노드V의 랭킹 보드(Max Heap)에 밀어 넣습니다(Push). 그리고 전체 탐색용 최소 힙(Min Heap) 큐에도(V, Cost)를 추가하여 이 길을 따라 계속 탐색을 이어가도록 합니다. - 랭킹 보드가 꽉 찼을 때 (이미 경로가 K개 기록됨):
새롭게 발견된Cost와, 현재 노드V의 랭킹 보드에서 가장 거리가 먼(Max Heap의 Peek) 꼴찌 랭커의 값을 대결시킵니다.- 만약 새로운
Cost가 꼴찌보다 더 크다면: 이 경로는 K등 안에도 들지 못하는 쓰레기 경로이므로 미련 없이 버립니다. - 만약 새로운
Cost가 꼴찌보다 더 작다면(더 짧다면): 꼴찌 랭커를 큐에서 쫓아내고(Pop), 새로운Cost를 랭킹 보드에 새롭게 등록(Push)합니다. 당연히 전체 탐색용 큐에도 넣어서 경로 탐색을 이어갑니다.
- 만약 새로운
3. 탐색의 종료와 시간 복잡도
일반 다익스트라는 노드가 큐에서 빠져나올 때(방문 처리 시) 더 이상 인접 노드를 보지 않지만, 이 변형된 알고리즘은 같은 노드를 여러 번 방문하는 것을 허용합니다. 목적지 노드의 랭킹 보드에 들어있는 요소의 개수가 K개가 되고, 탐색 큐가 완전히 텅 빌 때까지 이 지독한 경쟁은 계속됩니다.
모든 탐색이 종료된 후, 목적지 노드의 랭킹 보드(우선순위 큐)에서 맨 위에 있는 값(가장 큰 값)을 꺼내면, 그것이 바로 우리가 찾던 완벽한 K번째 최단 경로의 비용이 됩니다. 만약 큐의 사이즈가 K보다 작다면, 도달할 수 있는 경로가 K개가 채 안 된다는 뜻이므로 -1을 반환하면 됩니다.
이 알고리즘은 각 정점마다 K개의 상태를 유지해야 하므로, 시간 복잡도는 일반 다익스트라의 $O(E \log V)$에서 $O(K \cdot E \log V)$로 다소 무거워집니다. 따라서 문제에서 주어지는 K의 범위가 통상적으로 100 이하일 때만 안전하게 사용할 수 있는 고급 테크닉입니다.
1. K번째 최단 경로 알고리즘은 한 번 방문한 노드를 무시하는 기존 다익스트라의 한계를 벗어나, 다중 경로를 허용하는 상태 확장 탐색 기법입니다.
2. 각 노드마다 단일 최단 거리 변수 대신 내림차순 우선순위 큐(Max Heap)를 배치하여, 상위 K개의 경로 비용 랭킹을 지속적으로 갱신합니다.
3. 새로운 경로의 비용이 해당 노드의 K번째(꼴찌) 비용보다 작을 때만 큐를 갱신하며 탐색을 이어나가고, 시간 복잡도는 $O(K \cdot E \log V)$를 가집니다.