이 강좌에서는 자바스크립트를 활용하여 K번째 최단 경로를 찾는 알고리즘 문제를 다루어 보겠습니다. 이 문제는 그래프 이론과 경로 찾기 알고리즘의 탄탄한 이해를 요구하며, 효율적인 코드를 작성하는 데 초점을 맞추고 있습니다.
문제 설명
기본적으로 주어진 그래프에서 한 정점에서 다른 정점으로 가는 모든 가능한 경로 중에서 K번째로 짧은 경로의 총 길이를 찾아야 합니다.
문제 입력
- N: 정점의 개수 (1 ≤ N ≤ 100)
- M: 간선의 개수 (1 ≤ M ≤ 1000)
- K: 원하는 경로의 순위 (1 ≤ K ≤ 10)
- 이후 M개의 줄에 걸쳐 간선 정보를 입력받습니다.
각 간선 정보는 u, v, w로 구성되어 있으며, 이는 정점 u에서 정점 v로 가는 가중치가 w임을 의미합니다.
출력
K번째로 짧은 경로의 총 길이를 출력합니다. 만약 K번째로 짧은 경로가 존재하지 않을 경우에는 -1을 출력해야 합니다.
예제
입력 예시
4 5 2
1 2 4
1 3 2
3 2 5
2 4 1
3 4 3
출력 예시
5
문제 해결 접근법
K번째 최단 경로를 찾기 위해 여러가지 방법 중, 최적의 알고리즘은 다익스트라 알고리즘을 수정하여 사용하는 것입니다. 기본적으로 다익스트라 알고리즘은 가장 짧은 경로를 찾는 데에 사용되지만, K번째 최단 경로를 찾기 위해서는 경로를 여러 번 탐색할 수 있도록 해야 합니다.
단계별 풀이 과정
1. 그래프 표현
그래프는 인접 리스트 형태로 표현하며, 각 노드에는 연결된 노드와 그 경로의 가중치 정보를 저장합니다. 이를 통해 다익스트라 알고리즘을 효율적으로 적용할 수 있습니다.
2. 우선순위 큐 사용
Javscript의 PriorityQueue를 활용하여 가장 짧은 경로를 우선적으로 탐색합니다. 각 경로의 정보를 담고 있어, 다익스트라 알고리즘처럼 최소 비용부터 탐색할 수 있도록 설정합니다.
3. K번째 경로 탐색
경로를 탐색하며, K번째로 짧은 경로를 찾기 위한 카운트를 유지합니다. 경로의 길이를 배열에 저장하며, K번째로 도달한 경우 해당 길이를 반환하고, 그렇지 않으면 계속 탐색합니다.
4. 결과 출력
모든 경로를 탐색한 뒤, K번째 경로가 없을 경우 -1을 출력합니다.
구현 코드
아래의 코드는 위의 설명을 기반으로 K번째 최단 경로를 찾는 자바스크립트 버전입니다.
class MinHeap {
constructor() {
this.heap = [];
}
insert(node) {
this.heap.push(node);
this.bubbleUp();
}
bubbleUp() {
let index = this.heap.length - 1;
const element = this.heap[index];
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (element[1] >= parent[1]) break;
this.heap[index] = parent;
index = parentIndex;
}
this.heap[index] = element;
}
extractMin() {
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown();
}
return min;
}
sinkDown() {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild[1] < element[1]) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if ((swap === null && rightChild[1] < element[1]) ||
(swap !== null && rightChild[1] < leftChild[1])) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
index = swap;
}
this.heap[index] = element;
}
}
function kthShortestPath(n, edges, k) {
const graph = Array.from({ length: n + 1 }, () => []);
edges.forEach(([u, v, w]) => {
graph[u].push([v, w]);
});
const minHeap = new MinHeap();
const paths = Array.from({ length: n + 1 }, () => []);
minHeap.insert([1, 0]);
paths[1].push(0);
while (minHeap.heap.length > 0) {
const [node, distance] = minHeap.extractMin();
if (paths[node].length === k) continue;
for (const [neighbor, weight] of graph[node]) {
const newDistance = distance + weight;
if (paths[neighbor].length < k) {
paths[neighbor].push(newDistance);
paths[neighbor].sort((a, b) => a - b);
minHeap.insert([neighbor, newDistance]);
} else if (newDistance < paths[neighbor][paths[neighbor].length - 1]) {
paths[neighbor][paths[neighbor].length - 1] = newDistance;
paths[neighbor].sort((a, b) => a - b);
minHeap.insert([neighbor, newDistance]);
}
}
}
return paths[n][k - 1] || -1;
}
// 사용 예시
const n = 4;
const edges = [
[1, 2, 4],
[1, 3, 2],
[3, 2, 5],
[2, 4, 1],
[3, 4, 3],
];
const k = 2;
console.log(kthShortestPath(n, edges, k)); // 출력: 5
결론
이번 강좌에서는 K번째 최단 경로를 찾는 알고리즘에 대해 다루었습니다. 최단 경로 알고리즘을 기반으로 하여 문제를 해결할 수 있는 기법을 익혔습니다. 이러한 기초를 바탕으로 더 복잡한 그래프 문제를 해결할 수 있는 능력을 키울 수 있습니다.