다익스트라 알고리즘 학습 정리

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

다익스트라는 하나의 노드에서 다른 모든 노드까지의 최단 경로 및 거리를 구하는 알고리즘이다. 

주의할 점은 음수 간선이 존재하지 않을 때만 사용할 수 있다는 점.

중요한 시간 복잡도는 간선이 M이고, 노드 개수가 N일 때, O(M * logN)을 따르게 된다.

 

그림으로 이해하는게 더 빠른 것 같아서 직접 그려보며 공부해 보았다.

시작 노드부터 가까운 노드를 그리디하게 방문하는 점을 고려하면서 그려보니 이해하기 수월했다.

 

 

다익스트라 알고리즘 로직은 현재 살펴보지 않은 경로 중에서 가장 거리가 짧은 경로를 먼저 살펴봐야 한다. 힙 자료구조를 사용하게 되는데, 자바스크립트에서는 라이브러리가 제공되지 않기 때문에 우선순위 큐를 활용한 힙 자료구조를 직접 구현해야 했다.

 

우선순위 큐를 반영한 힙 자료구조 구현(JS)

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

    push(item) {
      this.items.push(item)
      this.bubbleUp()
    }

    pop() {
      if (this.size() === 0) {
        return
      }
      const min = this.items[0]
      this.items[0] = this.items[this.size() - 1]
      this.items.pop()
      this.bubbleDown()

      return min
    }

    swap(a, b) {
      [this.items[a], this.items[b]] = [this.items[b], this.items[a]]
    }

    bubbleUp() {
      let index = this.size() - 1
      while (index > 0) {
        const parentIndex = Math.floor((index - 1) / 2)
        if (this.items[parentIndex][0] < this.items[index][0]) {
          break
        }
        this.swap(index, parentIndex)
        index = parentIndex
      }
    }

    bubbleDown() {
      let index = 0
      while (index * 2 + 1 < this.size()) {
        let leftChild = index * 2 + 1
        let rightChild = index * 2 + 2

        let smallerChild = rightChild < this.size() && this.items[rightChild][0] < this.items[leftChild][0] ? rightChild : leftChild

        if (this.items[index][0] <= this.items[smallerChild][0]) {
          break
        }

        this.swap(index, smallerChild)
        index = smallerChild
      }
    }

    size() {
      return this.items.length
    }
  }

 

bubbleUp 함수와 bubbleDown 함수가 구현되어 있는데, 처음 보면 이해하기가 힘들고 낯설게 느껴진다. 먼저 bubbleUp과 bubbleDown은 힙의 정렬 상태를 유지하기 위해 사용되는 것이다. 위 코드는 최소힙을 구현한 것인데 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같아야 한다. 최대 힙은 반대로 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같아야 한다.

 

    bubbleUp() {
      let index = this.size() - 1
      while (index > 0) {
        const parentIndex = Math.floor((index - 1) / 2)
        if (this.items[parentIndex][0] < this.items[index][0]) {
          break
        }
        this.swap(index, parentIndex)
        index = parentIndex
      }
    }

 

bubbleUp은 새로 추가된 노드가 힙 속성을 만족하기 위해 위로 올라가면 정렬하는 작업을 수행한다.

힙의 끝에 새 값을 삽입하고, 새 값이 부모 값보다 작은 경우, 부모와 위치를 교환한다. 마지막으로 부모 노드로 이동하여 위 과정을 반복하게 된다.

 

bubbleDown() {
      let index = 0
      while (index * 2 + 1 < this.size()) {
        let leftChild = index * 2 + 1
        let rightChild = index * 2 + 2

        let smallerChild = rightChild < this.size() && this.items[rightChild][0] < this.items[leftChild][0] ? rightChild : leftChild

        if (this.items[index][0] <= this.items[smallerChild][0]) {
          break
        }

        this.swap(index, smallerChild)
        index = smallerChild
      }
    }

 

bubbleDown 함수는 최상단 노드가 힙 속성을 만족하도록 아래로 내려가며 정렬하는 작업을 수행한다.

최상단 값이 자식 값보다 크다면, 더 작은 자식과 위치를 교환하며, 작은 자식 노드로 이동하여 위 과정을 반복하게 된다. 

 

이처럼 다익스트라 알고리즘은 위와 같은 자료구조를 활용해서 경로들을 담고 짧은 경로부터 꺼내 탐색을 진행하게 된다.