다익스트라 알고리즘

그래프에서 한 노드에서 다른 노드까지의 최단 경로를 찾기 위한 알고리즘
가중치가 있는 그래프에서 사용되며, 가중치는 음수가 아니어야 함

다익스트라 알고리즘의 기본 원리

1. 초기화: 시작 노드의 거리를 0으로 설정하고, 나머지 모든 노드의 거리를 무한대로 설정
2. 방문 처리: 아직 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택
3. 경로 갱신: 선택된 노드를 경유하여 인접한 노드까지의 거리를 계산하고, 기존에 저장된 거리보다 짧다면 업데이트
4. 반복: 모든 노드가 방문될 때까지 2번과 3번을 반복

배열 예제

function dijkstra(graph, start) {
    const distances = Array(graph.length).fill(Infinity); // 모든 노드까지의 거리를 무한대로 초기화
    const visited = Array(graph.length).fill(false); // 방문 여부를 기록하는 배열
    distances[start] = 0; // 시작 노드의 거리를 0으로 설정

    function getSmallestUnvisitedNode() {
        let minDistance = Infinity;
        let minNode = -1;

        // 방문하지 않은 노드 중 가장 거리가 짧은 노드를 찾는다
        for (let i = 0; i < graph.length; i++) {
            if (!visited[i] && distances[i] < minDistance) {
                minDistance = distances[i];
                minNode = i;
            }
        }
        return minNode;
    }

    for (let i = 0; i < graph.length - 1; i++) {
        const node = getSmallestUnvisitedNode(); // 가장 거리가 짧은 노드를 선택
        visited[node] = true; // 선택된 노드를 방문 처리

        graph[node].forEach((edge) => {
            const [neighbor, weight] = edge;
            if (!visited[neighbor]) { // 방문하지 않은 이웃 노드에 대해서만 처리
                const newDistance = distances[node] + weight;
                if (newDistance < distances[neighbor]) { // 새로운 거리가 더 짧은 경우 업데이트
                    distances[neighbor] = newDistance;
                }
            }
        });
    }

    return distances; // 모든 노드까지의 최단 거리 배열을 반환
}

우선순위 큐 예제

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(value) {
        this.heap.push(value);
        this.heap.sort((a, b) => a.distance - b.distance); // 힙에 새 요소를 추가하고 거리에 따라 정렬
    }

    pop() {
        return this.heap.shift(); // 가장 작은 거리를 가진 요소를 제거하고 반환
    }

    isEmpty() {
        return this.heap.length === 0; // 힙이 비어있는지 확인
    }
}

function dijkstraWithHeap(graph, start) {
    const distances = Array(graph.length).fill(Infinity); // 모든 노드까지의 거리를 무한대로 초기화
    const minHeap = new MinHeap();
    distances[start] = 0;
    minHeap.push({ node: start, distance: 0 }); // 시작 노드를 힙에 추가

    while (!minHeap.isEmpty()) {
        const { node, distance } = minHeap.pop(); // 힙에서 거리가 가장 짧은 노드를 추출

        if (distance > distances[node]) continue; // 현재 노드까지의 거리가 이미 더 짧은 경우 스킵

        graph[node].forEach(([neighbor, weight]) => {
            const newDistance = distances[node] + weight; // 새로운 거리 계산
            if (newDistance < distances[neighbor]) { // 새로운 거리가 현재 거리보다 짧은 경우 업데이트
                distances[neighbor] = newDistance;
                minHeap.push({ node: neighbor, distance: newDistance }); // 업데이트된 거리와 함께 이웃 노드를 힙에 추가
            }
        });
    }

    return distances; // 모든 노드까지의 최단