data structures - Dijkstra 알고리즘

다익스트라(Dijkstra) 알고리즘이 뭘까?

다익스트라 알고리즘은 네트워크에서 한 노드에서 다른 노드로 가는 가장 짧은 경로를 찾는 알고리즘입니다. 1956년에 에츠허르 다익스트라에 의해 개발되었으며, 그래프 이론에서 중요한 위치를 차지합니다. 이 알고리즘은 양의 가중치를 가진 간선들을 포함하는 그래프에서 최단 경로 문제를 해결하는데 사용되고 인공위성 GPS 소프트웨어 등에서 가장 많이 사용되는 알고리즘이다.
다이나믹 프로그래밍에 속하며 “최단 거리가 여러 개의 최단 거리”로 이루어져 있기 때문이다. 즉, 하나의 최단 거리를 구할 때, 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 것입니다.

다익스트라 알고리즘 작동 방식
다음은 다익스트라 알고리즘이 어떻게 작동하는지에 대한 간단한 설명입니다.

1) 시작 노드를 설정합니다.
2) 시작 노드에서 각 노드까지의 거리를 추정합니다. 시작 노드의 경우 0으로, 다른 모든 노드의 경우 무한대로 설정합니다.
3) 미방문 노드 집합에서 최단 거리를 가진 노드를 선택합니다.
4) 해당 노드를 방문하고, 그 이웃 노드들의 거리를 업데이트 합니다.
5) 모든 노드를 방문할 때까지 이 과정을 반복합니다.

function dijkstra(graph, start) {
  let distances = {};
  for (let vertex in graph) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;

  let queue = new PriorityQueue();
  queue.enqueue(start, 0);

  while (!queue.isEmpty()) {
    let shortestDistanceVertex = queue.dequeue().element;
    for (let neighbor in graph[shortestDistanceVertex]) {
      let distanceThroughVertex = distances[shortestDistanceVertex] + graph[shortestDistanceVertex][neighbor];
      if (distanceThroughVertex < distances[neighbor]) {
        distances[neighbor] = distanceThroughVertex;
        queue.enqueue(neighbor, distances[neighbor]);
      }
    }
  }
  return distances;
}

우선 순위 큐를 사용하여 미방문 노드 중에서 가장 거리가 짧은 노드를 선택하고, 그 노드의 이웃 노드들의 거리를 업데이트하는 방식으로 작동합니다.