다익스트라 알고리즘

• 한 정점에서 다른 정점까지 가는 최단 경로

Reference BOJ | 최단 경로
1번 노드에 출발했을 때 그 외 노드에 방문할 수 있는 최단 경로를 구하는 문제이다.

초기 배열에는 자바스크립트 Infinity 값을 설정해준다. 배열을 그냥 편하게 dist라고 부르고자 한다면 dist[i] 는 1에서 i까지 갈 수 있는 최단 경로다. 따라서 dist[1]=0으로 초기화 시켜준다.

1에서 나아가는 경로를 체크한다.
2 ( 경로 구하는 경우 = dist[1] + 12 )가 dist[2] 보다 작다면 값을 교체해준다. 3( 경로 구하는 경우 = dist[1] + 4 ) 또한 마찬가지로 현재 경로가 기존 dist[3]보다 작다면 교체해준다.

1 (checked) 된 곳을 제외하고 2 ~ 6에서 가장 minimum한 값을 찾는다. 1에서 나아간 뒤 체크한다면 3이 checked 되는 것이다.

Minimum한 값을 찾을 때 배열을 순회하는 것은 O(N)이 걸리지만 최소 heap은 O(logN)이 걸리기 때문에 찾기 위해서는 최소 heap를 사용하는 것이 좋다

1에서 나아간 방향의 값을 찾았듯, checked 된 3에서 나아간 방향을 찾는다.

주의점

다익스트라를 이용할 때 그래프의 가중치는 반드시 양수여야 한다.

가중치가 음수인 경우는 벨만-포드 알고리즘을 이용해야 한다.

1. minHeap 구현

• 자바스크립트는 타 언어와 달리 우선순위 큐가 제공되지 않기 때문에 배열로 하면 o(N) 만큼의 시간이 걸린다. 그래서 대체로 minHeap 을 사용하여 시간복잡도를 단축시켜준다.

class MinHeap {
  constructor() {
    this.nodes = [];
  }
  insert(value) {
    this.nodes.push(value);
    this.upheap();
  }
  upheap() {
    let index = this.nodes.length - 1;
    let node = this.nodes[index];

    let parentNodeIndex = Math.floor((index - 1) / 2);
    while (index > 0 && node[1] < this.nodes[parentNodeIndex][1]) {
      this.nodes[index] = this.nodes[parentNodeIndex];
      index = parentNodeIndex;
      parentNodeIndex = Math.floor((index - 1) / 2);
    }
    this.nodes[index] = node;
  }
  downheap() {
    let index = 0;
    let node = this.nodes[index];

    while (index <= Math.floor((this.size() - 1) / 2)) {
      let childNodeIndex = index * 2 + 1;
      if (
        childNodeIndex < this.size() &&
        this.nodes[childNodeIndex + 1] &&
        this.nodes[childNodeIndex][1] > this.nodes[childNodeIndex + 1][1]
      ) {
        childNodeIndex += 1;
      }

      if (
        !this.nodes[childNodeIndex] ||
        node[1] <= this.nodes[childNodeIndex][1]
      ) {
        break;
      }

      this.nodes[index] = this.nodes[childNodeIndex];
      index = childNodeIndex;
    }
    this.nodes[index] = node;
  }
  get() {
    if (this.size() === 1) {
      return this.nodes.pop();
    }
    const node = this.nodes[0];
    this.nodes[0] = this.nodes.pop();
    this.downheap();
    return node;
  }
  size() {
    return this.nodes.length;
  }
}

플로이드 와샬

한 정점에서 모든 정점으로 가는 최단 경로를 구하는 다익스트라에 비해 플로이드 와샬은 모든 정점에서 모든 정점으로 가는 최단 경로를 구한다.

Reference BOJ | 2660 회장 뽑기

dist 라는 이차원 배열을 만들어 준다.

for(let i=1;i<=n;i++){
  for(let j=1;j<=n;j++){
    for(let k=1;k<=n;k++){
      dist[j][k]=Math.min(dist[j][k], dist[j][i]+dist[i][k];  
    }    
  }  
 }

플로이드 와샬은 위의 3중 for문만 기억해주면 된다.
dist[i][j]는 i에서 j까지 가는 최단거리를 의미한다.

개인적으로 플로이드 와샬을 사용하기 보다는 다익스트라로 간선마다 체크하는데 어떤 방식으로든 시간 차이가 많이 나지 않는 것 같다.. (?)