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

bkboy·2022년 6월 20일
JavaScript다익스트라알고리즘최소비용
0

알고리즘

목록 보기
10/14

다익스트라(Dijkstra)

다이나믹 프로그래밍을 활용한 대표적인 최단거리 알고리즘

선형 탐색을 활용한 다익스트라 알고리즘

const INF = Infinity;
const N = 6;
// 6 x 6 행렬
const graph = [
  [0, 2, 5, 1, INF, INF],
  [2, 0, 3, 2, INF, INF],
  [5, 3, 0, 3, 1, 5],
  [1, 2, 3, 0, 1, INF],
  [INF, INF, 1, 1, 0, 2],
  [INF, INF, 5, INF, 2, 0],
];

const visited = new Array(N).fill(0);
const dis = new Array(N).fill(0);

// 가장 최소 거리의 node(index)를 반환.
// 선형 탐색 => 기본적인 방법
const getMinIdx = () => {
  let min = INF;
  let idx = 0;
  for (let i = 0; i < N; i++) {
    if (min > dis[i] && !visited[i]) {
      min = dis[i];
      idx = i;
    }
  }
  return idx;
};

// 다익스트라 수행 함수
const dijkstra = (start) => {
  for (let i = 0; i < N; i++) {
    // graph의 start 행의 값으로 초기화.
    dis[i] = graph[start][i];
  }
  // 시작 노드 방문 처리
  visited[start] = 1;

  for (let i = 0; i < N; i++) {
    // dis배열에서 최소값
    let cur = getMinIdx();
    visited[cur] = 1;
    for (let j = 0; j < 6; j++) {
      if (!visited[j]) {
        if (dis[cur] + graph[cur][j] < dis[j]) {
          // start 노드에서 바로 j로 가는 비용이 cur노드를 거쳐서 j로 가는 비용보다 크다면
          // 값을 낮은 값으로 갱신
          dis[j] = dis[cur] + graph[cur][j];
        }
      }
    }
  }
};

dijkstra(0);

// start 노드에서 각 노드로 가는 최소 비용
for (let x of dis) {
  console.log(x);
}

선형 탐색을 이용한 다익스트라 알고리즘이다.

  1. 출발 노드를 설정한다.
  2. 출발 노드 기준으로 각 노드의 최소 비용을 저장한다.
  3. 방문하지 않은 노드를 중에서 가장 비용이 적은 노드를 선택한다.
  4. 해당 노드를 거쳐서 다른 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
  5. 모든 노드를 방문 할 때까지 3, 4 과정을 반복한다.

3번 과정에서 가장 비용이 적은 노드를 선택할 때 선형 탐색이 사용된 것이다.
이 알고리즘의 경우 시간 복잡도가 O(n^2)이 된다. 정점의 개수는 많은데 간선이 적을 떄 치명적이게 비효율적이다.

우선순위 큐를 활용한 다익스트라 알고리즘

힙에 대해선 정리해둔 글이 있다.

우선순위 큐는 힙 자료구조를 사용해 구현한다. 다익스트라 알고리즘의 과정 중 방문하지 않은 노드 중 비용이 가장 적게 드는 노드를 택 할때 최소 힙을 이용해서 찾게되면 시간 복잡도를 O(logN)으로 줄일 수 있다.

우선순위 큐는 리스트를 이용해서도 구현 할 수 있는데, 이 경우의 시간복잡도는 O(N)이다.

기존의 다익스트라 알고리즘 코드에는 최단 거리를 갱신하는 dis 배열과 방문 노드를 확인하는 visited 배열을 사용했지만 우선순위 큐를 이용하게 되면 최단 거리를 갱신하는 배열만 사용해도 된다. 우선순위 큐를 이용하게 되면 우선순위 큐가 알아서 최단 거리인 노드를 가장 앞으로 정렬해주기 때문에 기존에 기록한 최단 거리보다 크면 그냥 무시해주면 된다.

우선순위 큐를 먼저 구현해보겠다.

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

  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  peek = () => this.heap[0];

 // key, value로 받는 것으로 바뀌었다.
 insert = (key, value) => {
    const node = { key, value };
    this.heap.push(node);

    let cur = this.heap.length - 1;
    let parent = this.getParentIndex(cur);

    while (cur > 0 && this.heap[parent].key > this.heap[cur].key) {
      [this.heap[parent], this.heap[cur]] = [this.heap[cur], this.heap[parent]];
      cur = parent;
      parent = this.getParentIndex(cur);
    }
  };
	

// remove의 경우도 로직을 조금 바꾸었다. 주석을 보면 이해가 될 것이다.
  remove = () => {
    const count = this.heap.length;
    const rootNode = this.heap[0]; //keep

    if (count <= 0) return undefined;
    if (count === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    return rootNode;
  };
  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    // 원래 루트를 삭제하고 들어온 노드
    const rootNode = this.heap[index];

    // 왼쪽 자식의 인덱스가 heap의 길이보다 짧으면 왼쪽 자식은 존재
    // while문에 들어가지 않는다면 자식 노드가 존재하지 않는 것
    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      // 오른쪽 자식이 존재하고, 왼쪽 자식보다 값이 작다면 더 작은 값을 이 변수에
      // 오른쪽 자식이 없다면 자동적으로 이 변수엔 왼쪽 자식이 들어가게 됨.
      const smallerChildIndex =
        rightChildIndex < count &&
        this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
          ? rightChildIndex
          : leftChildIndex;
      // 그렇게 얻은 값이 루트의 값보다 작다면 값을 교환하고
      if (this.heap[smallerChildIndex].key <= rootNode.key) {
        this.heap[index] = this.heap[smallerChildIndex];
        // index값은 왼쪽, 오른쪽 중 작은 자식이 된다.
        index = smallerChildIndex;
      } else break;
    }

    // 마지막 index값이 원래 루트에 있던 노드의 자기 자리이다.
    this.heap[index] = rootNode;
  };
  size() {
    return this.heap.length;
  }
}

일반적인 최소 힙과는 다르게 key, value로 값을 받아온다. 

...
class PriorityQueue extends Heap {
  constructor() {
    super();
  }
  enqueue = (priority, value) => this.insert(priority, value);
  dequeue = () => this.pop();
  isEmpty = () => this.heap.length <= 1;
}

힙을 상속 받아 우선순위 큐를 만들었다.

다익스트라 함수

const dijkstra = (start) => {
  const dis = new Array(6).fill(Infinity);
  const queue = new PriorityQueue();

  // 시작점으로 가는 비용은 0임으로
  queue.enqueue(start, 0);

  while (queue.size()) {
    let { key: curNode, value: distance } = queue.dequeue();

    // 최단 거리가 아니라면 continue
    if (dis[curNode] < distance) continue;

    // 선택된 노드의 인접 노드들을 살펴본다.
    for (let i = 0; i < graph[curNode].length; i++) {
      let nextNode = i;
      let nextDistance = distance + graph[curNode][i];

      // 원래 알고 있던 비용보다 적다면 갱신
      if (nextDistance < dis[nextNode]) {
        dis[nextNode] = nextDistance;
        queue.enqueue(nextNode, nextDistance);
      }
    }
  }

  return dis;
};

bfs 방식으로 진행이 된다. 시작점과 시작점으로 가는 비용 0 을 넣고 시작한다. 반복문 차시마다 선택된 노드의 인접 노드들을 살피고 원래 알고있던 거리보다 짧은 거리가 나오면 갱신한다.

전체 코드

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

  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  peek = () => this.heap[0];

   insert = (key, value) => {
    const node = { key, value };
    this.heap.push(node);

    let cur = this.heap.length - 1;
    let parent = this.getParentIndex(cur);

    while (cur > 0 && this.heap[parent].key > this.heap[cur].key) {
      [this.heap[parent], this.heap[cur]] = [this.heap[cur], this.heap[parent]];
      cur = parent;
      parent = this.getParentIndex(cur);
    }
  };

  remove = () => {
    const count = this.heap.length;
    const rootNode = this.heap[0];

    if (count <= 0) return undefined;
    if (count === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    return rootNode;
  };
  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const rootNode = this.heap[index];

    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      const smallerChildIndex =
        rightChildIndex < count &&
        this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
          ? rightChildIndex
          : leftChildIndex;

      if (this.heap[smallerChildIndex].key <= rootNode.key) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }

    this.heap[index] = rootNode;
  };
  size() {
    return this.heap.length;
  }
}

class PriorityQueue extends Heap {
  constructor() {
    super();
  }

  enqueue = (priority, value) => this.insert(priority, value);
  dequeue = () => this.remove();
  isEmpty = () => this.heap.length <= 0;
}

const INF = Infinity;
const N = 6;
const graph = [
  [0, 2, 5, 1, INF, INF],
  [2, 0, 3, 2, INF, INF],
  [5, 3, 0, 3, 1, 5],
  [1, 2, 3, 0, 1, INF],
  [INF, INF, 1, 1, 0, 2],
  [INF, INF, 5, INF, 2, 0],
];

const edge = [];

const dijkstra = (start) => {
  const dis = new Array(6).fill(Infinity);
  const queue = new PriorityQueue();

  queue.enqueue(start, 0);

  while (queue.size()) {
    let { key: curNode, value: distance } = queue.dequeue();

    if (dis[curNode] < distance) continue;

    for (let i = 0; i < graph[curNode].length; i++) {
      let nextNode = i;
      let nextDistance = distance + graph[curNode][i];

      if (nextDistance < dis[nextNode]) {
        dis[nextNode] = nextDistance;
        queue.enqueue(nextNode, nextDistance);
      }
    }
  }

  return dis;
};

const answer = dijkstra(0);
console.log(answer);
profile
bkboy
음악하는 개발자
이전 포스트

Set 자료구조

다음 포스트

백트래킹(Backtracking)

0개의 댓글