다익스트라 알고리즘

• 다익스트라?

  • 다이나믹 프로그래밍을 이용한 최단 경로 알고리즘.
    • 다른 정점까지의 최단거리를 구할 때 이전의 값을 사용.(메모지에이션.)
  • 단, 음의 간선이 있는 경우 사용할 수 없음.(왜?)
    • 무한 루프가 가능해서? -> 방문한 정점을 다시 안가게 하면 어떨까? 하지만 방문한 정점을 안가게 하면 그 정점이 값이 바뀌는 경우에 대처를 못함.
      • 그래서 방문을 사용하는 경우에는 값이 바뀌면 방문을 false 다시 바꿔주고, 끝나는 조건을 모든 정점이 true인 경우로 해줘야 한다.
      • 그래서 음의 가중치가 있으면 계속 갱신이 되기 때문에 안된다.
      • 방문을 사용하지 않으면, 현재 distance와 과거 distance를 비교해서 현재 distance가 과거 distance보다 작다면, 다시 queue에 넣을 필요가 없다.

• 작동 원리

  1. 특정 하나의 정점으로부터 시작.
  2. 이웃한 정점들에서 비용이 가장 작은 노드를 선택(방문하지 않은 노드여야 함).
  3. 선택한 노드에서 다른 노드 까지 가는 비용을 업데이트(거쳐서 간다는 느낌. 만약 1->2 로 가는거보다 1->3->2로 가는게 작다면 갱신됨.)
  4. 2.3번 을 반복하여 모든 정점을 방문할 때 까지 반복.

• 코드

const setArray = (n, fillValue) => Array(n + 1).fill(fillValue);

const setTwoDimensionArr = (n, fillValue) =>
  Array.from(Array(n + 1), () => Array(n + 1).fill(fillValue));

// 양방향 그래프
const setEdges = (edges, twoDimArr) => {
  edges.forEach(edge => {
    const [x, y, cost] = edge;
    twoDimArr[x][y] = cost;
    twoDimArr[y][x] = cost;
  });
};

// 양방향 그래프
const dijkstra = (vertexs, edges, start) => {
  const visited = setArray(vertexs, false);
  const distance = setArray(vertexs, Infinity);
  const adj = setTwoDimensionArr(vertexs, Infinity);

  // 특정 시작 정점을 0으로 설정.
  distance[start] = 0;
  const queue = [start];
  //인접 정점들 코스트.
  setEdges(edges, adj);

  while (visited.every(e !== true)) {
    const startVertex = queue.shift();
    // 최소 노드를 찾기 위한 min과 minVertex
    let min = Infinity;
    let minVertex = -1;
    visited[startVertex] = true;
    for (let i = 1; i < adj.length; i++) {
      if (startVertex === i) continue;
      distance[i] = Math.min(
        distance[i],
        distance[startVertex] + adj[startVertex][i]
      );
      // 가장 작은 cost값을 찾기 위한 조건문.
      if (distance[i] < min) {
        visited[i] = false;
        min = distance;
        minVertex = i;
      }
    }
    if (minVertex === -1) break;
    queue.push(minVertex);
  }
  return distance;
};

하지만 이 코드의 경우, adj를 만들 때, 2차원 배열을 사용하므로 공간 복잡도가 nn이다. 그리고, 해당 정점에 인접한 값을 찾아야하기 때문에, nn의 시간복잡도를 가진다. (정점은 1부터 시작한다고 가정.배열의 인덱스를 맞추기 위해 0 인덱스는 제외.)

우선순위큐(heap자료구조)를 사용하면, heap은 이진트리로 만들고, 이진트리의 복잡도는 Nlog2 N(로그 2의 N)의 값을 가지기 때문에,
우선순위큐를 사용할 때, 시간복잡도가 더 줄어든다.

Min heap을 사용한 다익스트라 알고리즘.(단방향)

Heap

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

  add(value) {
    this.arr.push(value);
    this._heapify();
  }

  pop() {
    if (this.size() === 0) return -1;
    const temp = this.arr.pop();
    const returnValue = this.arr[1];
    if (this.size() === 0) return temp;
    this.arr[1] = temp;
    this._heapify2();
    return returnValue;
  }

  size() {
    return this.arr.length - 1;
  }

  _heapify() {
    const heap = this.arr;
    let child = heap.length - 1;
    let parent = Math.floor(child / 2);
    while (parent !== 0) {
      if (heap[parent][1] <= heap[child][1]) break;
      const temp = heap[parent];
      heap[parent] = heap[child];
      heap[child] = temp;
      child = parent;
      parent = Math.floor(child / 2);
    }
  }
  _heapify2() {
    const heap = this.arr;
    let parent = 1;
    let left = parent * 2;
    let right = parent * 2 + 1;

    while (heap[left] !== undefined || heap[right] !== undefined) {
      if (heap[right] === undefined) {
        if (heap[left][1] > heap[parent][1]) break;
        this._change(left, parent, heap);
        break;
      }
      if (heap[left][1] <= heap[right][1]) {
        if (heap[left][1] > heap[parent][1]) break;
        [parent, left, right] = this._change(left, parent, heap);
      } else {
        if (heap[right][1] > heap[parent]) break;
        [parent, left, right] = this._change(right, parent, heap);
      }
    }
  }

  _change(child, parent, heap) {
    const temp = heap[parent];
    heap[parent] = heap[child];
    heap[child] = temp;
    parent = child;
    const left = parent * 2;
    const right = parent * 2 + 1;
    return [parent, left, right];
  }
}

module.exports = Heap;

다익스트라 알고리즘

const dijkstraHeap = (vertexs, edges, start) => {
  const adj = Array(vertexs + 1);
  edges.forEach(edge => {
    if (!adj[edge[0]]) adj[edge[0]] = [];
    adj[edge[0]].push([edge[1], edge[2]]);
  });

  const distance = setArray(vertexs, Infinity);

  const heap = new Heap();
  let startVertex = [start, 0];
  heap.add(startVertex);
  distance[start] = 0;

  while (heap.size()) {
    const [index, value] = heap.pop();
    if (!adj[index]) continue;
    if (distance[index] < value) continue;
    adj[index].forEach(edge => {
      const [vertex, value] = edge;
      if (distance[vertex] <= distance[index] + value) return;
      distance[vertex] = distance[index] + value;
      heap.add([vertex, distance[vertex]]);
    });
  }
  return distance;
};