[알고리즘] 다익스트라 (Dijkstra`s Algorithm)

다익스트라는 그래프에서 모든 정점 까지의 최단 거리를 구하는 대표적인 알고리즘이다.

위의 그래프 처럼 각 경로에 가중치가 있을 경우 특히 유용하고,

가중치가 없는 경우에는 개인적으로 BFS를 사용하는게 더 유용했던 것 같다.

 

다익스트라 알고리즘을 이용할 때는 완전 이진트리 형태로 최소값을 꺼내기 유용한 Minheap(최소힙) 구조를 사용한다.

Min Heap

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

  insert(value) {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

  heapifyUp(index) {
    while (index > 0) {
      const parentIndex = (index - 1) >> 1;
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

  remove() {
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.heapifyDown(0);
    }
  }

  heapifyDown(index) {
    while (index < this.heap.length) {
      const left = (index << 1) + 1;
      const right = (index << 1) + 2;
      let smallest = index;
      if (this.heap[left] && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }
      if (this.heap[right] && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ];
      index = smallest;
    }
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

- 보다시피 루트는 항상 가장 작은 값을 가지고, 값을 삽입할 때마다 정렬하여 최소값을 만드는 방식이다.

 

다익스트라

 

function dijkstra(graph, start) {
    const dist = Array(graph.length).fill(Infinity);
    dist[start] = 0;
    const pq = new MinHeap();
    pq.push([0, start]); // [거리, 노드]

    while (!pq.isEmpty()) {
        const [curDist, u] = pq.pop();
        if (dist[u] < curDist) continue;

        for (const [v, weight] of graph[u]) {
            const newDist = curDist + weight;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                pq.push([newDist, v]);
            }
        }
    }

    return dist;
}

1. 그래프는 [시작, 도착, 가중치]를 요소로 가지고 있는 배열을 시작점 - [도착점, 가중치] 배열로 만들어둔 무방향 그래프나 방향그래프를 사용한다고 가정한다.

2. 해당 그래프의 시작지점에서 도착지점까지의 거리를 전체적으로 Infinity(무한)로 지정한다.

3. 시작점에서 부터 시작점까지 거리는 0이고 최소 거리와 시작 노드를 넣어서 각 목적지까지 도착했을 때 거리를 순회하면서 계산

4. dist로 반환한 배열에 도착지 번째 요소에 해당 도착지까지 최소 가중치를 통해서 도착할 수 있는 경로의 거리를 반환한다.

 

참고자료:

https://velog.io/@ahhpc2012/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-Javascript

다익스트라 알고리즘 (with Javascript)