다익스트라(Dijkstra) 알고리즘

그래프와 이진 힙을 사용한 우선순위 큐를 알아야 한다.

 

다익스트라 알고리즘의 목적은 그래프의 두 정점(vertex) 사이에 존재하는 최단 경로를 찾는 것이다.

- 서울에서 부산으로 가는 최단경로(GPS)

- 인간 사이의 바이러스의 감염 경로

- 목적지까지의 가장 저렴한 경로

 

이를 위해 선행되어야 하는 작업은 두 정점 사이에 가중치(예를 들면 거리) 가 존재하도록 해야 한다는 것이다. 

이전 포스팅에서는 양방향 무가중치 그래프만을 다뤘다.

그래프(Graph)

여기서는 가중치 그래프를 다룬다. 큰 차이점은 정점이 가지고 있는 리스트에 단순히 다른 정점이 추가되는 것이 아니라, 정점과 가중치가 추가된다는 것이다. 따라서 여기서는 정점과 가중치를 객체의 속성으로 하여 저장하는 방식을 사용한다.

 

class WeightedGraph {
    constructor() {
        // 인접리스트. 지만 객체로 관리
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        // 인접리스트 객체에 없으면 프로퍼티로 추가하고 빈 배열을 값으로 준다. 존재하면 아무 작업도 수행하지 않는다.
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }

    addEdge(vertex1, vertex2, weight) {
        this.adjacencyList[vertex1].push({node: vertex2, weight});
        this.adjacencyList[vertex2].push({node: vertex1, weight});
    }
}

 

가중치 그래프의 기본적인 구조는 위와 같다.

 

아래는 가중치 그래프와 우선순위 큐를 사용하여 구현한 다익스트라 알고리즘이다.

 

// 다익스트라 알고리즘은 가중치 그래프로 구성된 자료구조에서 메서드로서 작동될 수 있다.
// 

class WeightedGraph {
    constructor() {
        this.adjacencyList = {};
    }

    // 정점 추가
    addVertex(vertex) {
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
        // 이로써 여러 정점들이 인접리스트 객체 내에 키(문자열):밸류(배열) 형태로 들어가게 된다. 
    }

    // 간선 추가
    addEdge(vertex1, vertex2, weight) {
        if(!this.adjacencyList[vertex1] || !this.adjacencyList[vertex2]) return null;
        this.adjacencyList[vertex1].push({node: vertex2, weight});
        this.adjacencyList[vertex2].push({node: vertex1, weight});

        /* 만약 방향 그래프라면 하나만 한쪽에만 넣어주면 된다. */
    }


    /* 다익스트라 메서드 : 여기서는 최단경로를 찾는다.*/
    Dijkstra(start, finish) {
        // 우선순위 큐 생성 (최단 거리가 가장 짧은 노드를 먼저 처리하기 위함)
        const priorityQ = new PriorityQueue();
        
        // 시작점으로부터 각 정점까지의 최단 거리를 저장할 객체
        // 예: { "A": 0, "B": 4, "C": 2, ... }
        const distances = {};
        
        // previous는 최단 경로를 추적하기 위한 객체이다. (각 정점의 이전 정점을 저장)
        // 예: { "B": "A", "C": "A", ... } -> B까지 가는 최단 경로의 이전 정점은 A
        const previous = {};
        
        // 최종 경로를 저장할 배열
        let path = [];
        let smallest;

        // 초기화: 모든 정점의 거리를 Infinity로, 시작점은 0으로 설정
        for(let vertex in this.adjacencyList) {
            if(vertex === start) {
                distances[vertex] = 0;
                priorityQ.enqueue(vertex, 0);
            } else {
                distances[vertex] = Infinity;
                priorityQ.enqueue(vertex, Infinity);
            }
            previous[vertex] = null;
        }

        // 우선순위 큐가 빌 때까지 반복
        while(priorityQ.values.length) {
            // 현재 가장 가까운 정점을 가져옴
            smallest = priorityQ.dequeue().val;
            
            // 목적지에 도달했다면
            if(smallest === finish) {
                // 경로 재구성
                while(previous[smallest]) {
                    path.push(smallest);
                    smallest = previous[smallest];
                }
                break;
            }

            // 현재 정점이 유효하고 아직 방문하지 않은 경우
            if(smallest || distances[smallest] !== Infinity) {
                // 현재 정점의 이웃들을 순회
                for(let nextNode of this.adjacencyList[smallest]) {
                    // 현재까지의 거리 + 현재 간선의 가중치 계산
                    let candidate = distances[smallest] + nextNode.weight;
                    let nextNeighbor = nextNode.node;

                    // 더 짧은 경로를 찾은 경우
                    if(candidate < distances[nextNeighbor]) {
                        // 최단 거리 업데이트
                        distances[nextNeighbor] = candidate;
                        // 경로 추적을 위해 이전 정점 정보 업데이트
                        previous[nextNeighbor] = smallest;
                        // 우선순위 큐에 새로운 정보 추가
                        priorityQ.enqueue(nextNeighbor, candidate);
                    }
                }
            }
        }
        // 시작점을 포함하여 경로를 완성하고 올바른 순서로 반환
        return path.concat(smallest).reverse();
    }
}


class PriorityQueue {
    constructor() {
        this.values = [];
    }

    enqueue(val, priority) {    // 값과 우선순위
        let newNode = new Node(val, priority);
        this.values.push(newNode);
        this.bubbleUp();
    }

    bubbleUp() {
        let idx = this.values.length - 1;
        const element = this.values[idx];
        while(idx > 0) {
            // 부모에서 자식을 찾을 때 -> 2n+1(좌), 2n+2(우) 이므로
            // 자식에서 부모를 찾기 위해 역으로 계산한다. Math.floor((자식인덱스-1)/2)
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.values[parentIdx];

            // 최소 힙이기 때문에 우선순위가 작은 것이 부모 위치에 있게 된다. 따라서 탈출
            if(element.priority >= parent.priority) break;

            this.values[idx] = this.values[parentIdx];
            this.values[parentIdx] = element;

            idx = parentIdx;    // 부모 위치로 이동
        }
    }

    dequeue() {
        const min = this.values[0]; //왜냐하면 최소힙이기 때문에 우선순위 큐의 맨 앞은 최소값이다.
        const end = this.values.pop();

        if(this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }

        return min; // 조건문 이전에 리턴해도 된다.
    }

    /* 가장 낮은 우선순위를 가진 노드가 맨 앞(루트 노드)에 왔을 때 자식 노드들과 비교해가며 적합한 위치를 찾도록 하는 목적*/
    sinkDown() {
        let idx = 0;
        const length = this.values.length;
        let element = this.values[0];   //루트노드에 최소 우선순위가 와 있으므로 0부터 시작

        while(true) {
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let swap = null;    // 바꿀 인덱스를 저장하는 변수

            let leftChild;
            let rightChild;

            // 루트 노드에 올라온 최솟값을 왼쪽-오른쪽 자식의 우선순위와 번갈아가며 확인한다.
            // 먼저 대상 노드의 우선순위를 왼쪽과 비교하여 swap(임시값)을 정하고, 
            // 그 이후 오른쪽 노드의 우선순위와 비교하여 swap의 값을 확정한 뒤 노드의 위치를 교체한다.

            // 우선 왼쪽부터
            if(leftChildIdx < length) {
                leftChild = this.values[leftChildIdx];
                // 왼쪽자식의 우선순위가 높다면(숫자값은 낮음), 스왑에 자식의 인덱스를 담는다
                if(leftChild.priority < element.priority) {
                    swap = leftChildIdx
                }
            }

            // 이제 오른쪽: swap이 null이 아닌 경우, 왼쪽자식과의 우선순위를 비교해야 한다는 점에 주의.
            if(rightChildIdx < length) {
                rightChild = this.values[rightChildIdx];
                if(
                    swap === null && rightChild.priority < element.priority ||
                    swap !== null && rightChild.priority < leftChild.priority
                   ) {
                    swap = rightChildIdx;
                }
            }

            // 스왑이 널이라는 의미는 자식들의 우선순위보다 대상 노드의 우선순위가 높다는 것이므로 탈출
            if(swap === null) break;

            this.values[idx] = this.values[swap];
            this.values[swap] = element;
            idx = swap;

        }
    }

}

class Node {
    constructor(val, priority) {
        this.val = val;
        this.priority = priority;
    }
}

 

예시 코드

 

// 그래프 생성
const graph = new WeightedGraph();

// 정점 추가
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");

// 간선 추가 (무방향 그래프)
graph.addEdge("A", "B", 3);  // A-B 거리 3
graph.addEdge("A", "C", 2);  // A-C 거리 2
graph.addEdge("B", "D", 4);  // B-D 거리 4
graph.addEdge("C", "D", 1);  // C-D 거리 1

/*

	3
   A ----- B
   |       |
 2 |       | 4
   |       |
   C ----- D
      1

*/

// 최단 경로 찾기
console.log("A에서 D까지의 최단 경로:", graph.Dijkstra("A", "D"));
// 출력: ["A", "C", "D"]

// 그래프의 구조 확인
console.log("그래프의 인접 리스트:", graph.adjacencyList);
/* 출력:
{
  "A": [
    { "node": "B", "weight": 3 },
    { "node": "C", "weight": 2 }
  ],
  "B": [
    { "node": "A", "weight": 3 },
    { "node": "D", "weight": 4 }
  ],
  "C": [
    { "node": "A", "weight": 2 },
    { "node": "D", "weight": 1 }
  ],
  "D": [
    { "node": "B", "weight": 4 },
    { "node": "C", "weight": 1 }
  ]
}
*/