다익스트라 알고리즘

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


그래프 내 여러개 노드가 있을 때, 특정노드에서 출발해
다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘

원리

1. 출발 노드를 설정

2. 최단거리 테이블 초기화

3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택

4. 해당 노드 거쳐 다른 노드로 가는 비용 계산해 최단거리 테이블 생성

5. 3번과 4번 반복

 

 

간단한 다익스트라 (JS)

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, s, ...rest] = input;
const [n, m] = nm.split(' ').map((v) => +v);
const start = +s;
const arr = rest.map((str) => str.split(' ').map((v) => +v));

let visited = [...Array(n + 1).fill(false)];
let d = [...Array(n + 1).fill(Infinity)];

function solution(n, m, start, arr) {
  //초기화
  const graph = Array.from(Array(n + 1), () => []);
  for (const v of arr) {
    const [a, b, c] = v;
    graph[a].push([b, c]);
  }

  //방문하지 않은 노드에서 최단 거리가 가장 짧은 노드의 인덱스 반환
  const getSmallestNode = () => {
    let min = Infinity;
    let index = 0;
    for (const i in d) {
      if (!visited[i] && min > d[i]) {
        min = d[i];
        index = i;
      }
    }
    return index;
  };

  const dijkstra = (start) => {
    //시작 노드 초기화
    d[start] = 0;
    visited[start] = true;
    for (const i of graph[start]) {
      const [node, cost] = i;
      d[node] = cost;
    }

    //시작 노드를 제외한 전체 노드에 대해 반복
    for (let i = 0; i < n; i++) {
      const cur = +getSmallestNode();
      visited[cur] = true;

      for (const j of graph[cur]) {
        const node = j[0];
        const cost = d[cur] + j[1];
        if (cost < d[node]) {
          d[node] = cost;
        }
      }
    }
  };

  dijkstra(start);

  for (let i = 1; i <= n; i++) {
    if (d[i] === Infinity) {
      console.log('INFINITY');
    } else {
      console.log(d[i]);
    }
  }

  return d;
}

console.log(solution(n, m, start, arr));

 

 

개선된 다익스트라

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, s, ...rest] = input;
const [n, m] = nm.split(' ').map((v) => +v);
const start = +s;
const arr = rest.map((str) => str.split(' ').map((v) => +v));

let d = [...Array(n + 1).fill(Infinity)];

function solution(n, m, start, arr) {
  const graph = Array.from(Array(n + 1), () => []);
  for (const v of arr) {
    const [a, b, c] = v;
    graph[a].push([b, c]);
  }

  const dijkstra = (start) => {
    //시작 노드 초기화
    const pq = new PriorityQueue();
    pq.push([0, start]); //[거리, 노드]
    d[start] = 0;

    while (!pq.empty()) {
      const [dist, cur] = pq.pop(); //현재 최단 거리가 가장 짧은 노드

      //최단 거리가 아닌 경우(방문한 적이 있는 경우) 스킵
      if (d[cur] < dist) continue;

      for (const i of graph[cur]) { //인접 노드 탐색
        const node = i[0];
        const cost = dist + i[1];
        if (cost < d[node]) {
          pq.push([cost, node]);
          d[node] = cost;
        }
      }
    }
  };

  dijkstra(start);

  for (let i = 1; i <= n; i++) {
    if (d[i] === Infinity) {
      console.log('INFINITY');
    } else {
      console.log(d[i]);
    }
  }

  return d;
}

console.log(solution(n, m, start, arr));

 

우선순위 큐 구현

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

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

  peek() {
    return this.heap[0];
  }

  push(data) {
    this.heap.push(data);

    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = ~~((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }

  pop() {
    if (this.empty()) return;

    const value = this.peek();
    [this.heap[0], this.heap[this.heap.length - 1]] = [
      this.heap[this.heap.length - 1],
      this.heap[0],
    ];
    this.heap.pop();
    this._heapify();
    return value;
  }

  _heapify() {
    const x = this.peek();
    const n = this.heap.length;
    let cur = 0;

    while (2 * cur + 1 < n) {
      const leftChild = 2 * cur + 1;
      const rightChild = leftChild + 1;
      const smallerChild =
        rightChild < n && this.heap[rightChild] < this.heap[leftChild]
          ? rightChild
          : leftChild;

      //루트 노드의 값이 더 큰 경우 swap
      if (x > this.heap[smallerChild]) {
        [this.heap[cur], this.heap[smallerChild]] = [
          this.heap[smallerChild],
          this.heap[cur],
        ];
        cur = smallerChild;
      } else {
        break;
      }
    }
  }
}

const pq = new PriorityQueue();
pq.push(3);
pq.push(5);
pq.push(2);
pq.pop();
pq.push(6);
pq.push(1);
pq.pop();

while (!pq.empty()) {
  console.log(pq.pop());
}

 

 

출처

https://hyerm-coding.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F