자바스크립트로 구현하는 다익스트라(Dijkstra) 알고리즘 완벽 가이드

다익스트라 알고리즘이란?

다익스트라(Dijkstra) 알고리즘은 가중치 그래프(weighted graph)에서 노드 간의 최단 경로를 찾는 대표적인 알고리즘입니다. 그래프를 생성할 때 간선에 가중치를 부여하려면 앞서 소개한 addEdge와 addDirectedEdge 메서드를 활용합니다.

알고리즘 동작 원리

다익스트라 알고리즘은 다음과 같은 순서로 동작합니다.

거리(distances) 컬렉션 생성 — 시작 노드를 제외한 모든 정점의 거리를 무한대(Infinity)로 초기화합니다.
시작 노드를 우선순위 큐에 삽입 — 시작 노드의 거리는 0이므로, 우선순위 0으로 최소 우선순위 큐(min-priority queue)에 넣습니다.
반복 처리 — 우선순위 큐가 빌 때까지 반복하며, 큐에서 거리가 가장 작은 노드를 꺼냅니다(dequeue).
거리 갱신 — 꺼낸 노드와 연결된 이웃 노드들에 대해 "현재 노드까지의 거리 + 간선 가중치 < 다음 노드의 기존 거리" 조건을 만족하면 거리를 갱신하고, 새로운 거리와 함께 해당 노드를 큐에 다시 삽입합니다.
우선순위 큐가 빌 때까지 위 과정을 계속 진행합니다.

이 알고리즘의 핵심 아이디어는 모든 노드가 시작점으로부터 무한대 거리에 있다고 가정하는 것입니다. 이후 간선들을 하나씩 고려하면서 시작점으로부터 각 노드까지의 거리를 추적하고, 도중에 더 낮은 비용의 경로를 발견하면 그때마다 값을 갱신해 나갑니다.

자바스크립트 구현

아래는 다익스트라 알고리즘을 자바스크립트로 구현한 코드입니다.

djikstraAlgorithm(startNode) {
    let distances = {};

    // 이전 노드에 대한 참조를 저장
    let prev = {};
    let pq = new PriorityQueue(this.nodes.length * this.nodes.length);

    // 시작 노드를 제외한 모든 노드의 거리를 무한대로 설정
    distances[startNode] = 0;
    pq.enqueue(startNode, 0);
    this.nodes.forEach(node => {
        if (node !== startNode) distances[node] = Infinity;
        prev[node] = null;
    });

    while (!pq.isEmpty()) {
        let minNode = pq.dequeue();
        let currNode = minNode.data;
        let weight = minNode.priority;
        this.edges[currNode].forEach(neighbor => {
            let alt = distances[currNode] + neighbor.weight;
            if (alt < distances[neighbor.node]) {
                distances[neighbor.node] = alt;
                prev[neighbor.node] = currNode;
                pq.enqueue(neighbor.node, distances[neighbor.node]);
            }
        });
    }
    return distances;
}

예제 실행

실제 그래프를 만들어 알고리즘을 테스트해 보겠습니다.

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addDirectedEdge("A", "C", 100);
g.addDirectedEdge("A", "B", 3);
g.addDirectedEdge("A", "D", 4);
g.addDirectedEdge("D", "C", 3);
g.addDirectedEdge("D", "E", 8);
g.addDirectedEdge("E", "F", 10);
g.addDirectedEdge("B", "G", 9);
g.addDirectedEdge("E", "G", 50);

console.log(g.djikstraAlgorithm("A"));

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

{ A: 0, B: 3, C: 7, D: 4, E: 12, F: 22, G: 12 }

결과를 해석해 보면, 시작 노드 A로부터 각 노드까지의 최단 거리를 의미합니다. 예를 들어 노드 C로 가는 직접 간선의 가중치는 100이지만, D를 경유하면 4 + 3 = 7이라는 훨씬 짧은 경로를 찾을 수 있습니다. 이처럼 다익스트라 알고리즘은 겉보기에 비싼 직접 경로 대신, 여러 간선을 조합한 더 저렴한 경로를 효율적으로 탐색해 줍니다.