[Algorithm]다익스트라 알고리즘, 플로이드 워셜 알고리즘

최단거리 구하는 알고리즘에는 크게 두 분류가 있다.
첫번째 노드 사이의 거리가 동일 할 때 (DFS, BFS 방식의 알고리즘을 사용)
두번째 노드 사이의 거리가 가중치가 있을 때는 다익스트라 알고리즘 또는 플로이드 워셜 알고리즘을 사용한다.

다익스트라 알고리즘의 목적은 두 노드 사이의 최단 거리를 구하는 알고리즘이고,
플로이드 워셜 알고리즘은 모든 노드간의 최단거리를 구하는 알고리즘이다.

결과론 적으로 다익스트라 알고리즘은 srcVertex에서 distVertex까지 가는 경로와, 각 경로까지 가는데 걸리는 거리를 나타내 준다.
(ex [A, C, D, B,E], {A:2, B:10, C:5, D:8, E:12}

플로이드 워셜 알고리즘의 결과로는 n * n의 표를 통해 모든 노드간의 거리를 확인할 수 있다.

플로이드 워셜 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘은 srcVertex-> distVertex에서 srcVertex->mid->distVertex로 변형하여서, mid에 모든 노드를 대입해본다.

기본 베이스가 되는 플로이드 워셜 알고리즘의 표는 아래와 같다.

A B C D E
A 0 INF INF INF INF
B INF 0 INF INF INF
C INF INF 0 INF INF
D INF INF INF 0 INF
E INF INF INF INF 0

그리고 위에서 말한 바와 같이 mid를 A에서부터 E까지 진행해 준다.

graph[start][end] = Math.min(graph[start][end], graph[start][mid] + graph[mid][end])

다익스트라 알고리즘

우선순위 큐를 통해 우선순위가 높은(거리가 짧은) 노드부터 기준을 삼아, 그 노드까지 가는데 걸리는 비용을 최소가 되도록 지속해서 최신화 시켜준다.

우선순위 큐

function PriorityQueue() {
  this.values = [];
}

PriorityQueue.prototype.enqueue = function (val, priority) {
  this.values.push({ val, priority });
  this.sort();
};

PriorityQueue.prototype.dequeue = function () {
  return this.values.shift();
};

PriorityQueue.prototype.sort = function () {
  this.values.sort((a, b) => a.priority - b.priority);
};

다익스트라 알고리즘 구현

Edge, Vertex추가

function WeightedGrah() {
  this.adjacencyList = {};
}

WeightedGrah.prototype.addVertex = function (vertex) {
  if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
};

WeightedGrah.prototype.addEdge = function (srcVertex, distVertex, weight) {
  this.adjacencyList[srcVertex].push({ node: distVertex, weight });
  this.adjacencyList[distVertex].push({ node: srcVertex, weight });
};

다익스트라 알고리즘

WeightedGrah.prototype.dijkstra = function (start, finish) {
  const nodes = new PriorityQueue();
  //우선순위 큐를 통해 BFS와 비슷하게 진행을 한다.
  nodes.enqueue(start, 0);

  const distances = {};
  const previous = {};
  const path = [];

  let smallest;
  // 다음과 같은 초기 상태를 만들기 위해 for문을 돌린다.
  // distances { A: 0, B: Infinity, C: Infinity, D: Infinity, E: Infinity, F: Infinity}
  // previous { A: null, B: null, C: null, D: null, E: null, F: null }
  for (const vertex in this.adjacencyList) {
    if (vertex === start) {
      distances[vertex] = 0;
    } else {
      distances[vertex] = Infinity;
    }
    previous[vertex] = null;
  }

  while (true) {
    smallest = nodes.dequeue().val;
    if (smallest === finish) {
      while (previous[smallest]) {
        path.push(smallest);
        smallest = previous[smallest];
      }
      break;
    } else {
      for (const neighbor in this.adjacencyList[smallest]) {
        //거리가 최소화 되는길을 바탕으로 계속 최신화 해 나간다.
        const nextNode = this.adjacencyList[smallest][neighbor];

        const candidate = distances[smallest] + nextNode.weight;
        const nextNeighbor = nextNode.node;

        if (candidate < distances[nextNeighbor]) {
          distances[nextNeighbor] = candidate;
          previous[nextNeighbor] = smallest;
          nodes.enqueue(nextNeighbor, candidate);
        }
      }
    }
  }
  return [path.concat(smallest).reverse(), distances];
};