[알고리즘] 다익스트라(Dijkstra) 알고리즘을 활용한 최단 경로 탐색

카테고리 : 컴퓨터 공학
태그: cs · 컴퓨터 공학 · algorithm · Dijkstra · 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘을 활용한 최단 경로 탐색

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 출발점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘으로, 널리 사용되는 최단 경로 알고리즘 중 하나다.

알고리즘 동작 방식

  1. 출발점을 설정하고 출발점의 최단 거리를 0으로 초기화. 다른 모든 정점들의 최단 거리는 무한대로 초기화.
  2. 현재까지 최단 거리가 확정되지 않은 정점들 중에서 가장 최소 거리를 가진 정점을 선택. 이를 “확정되지 않은 정점 집합”에서 선택하는 과정.
  3. 선택한 정점과 연결된 다른 정점들에 대해, 현재까지의 최단 거리와 연결된 간선의 가중치를 고려하여 최단 거리를 갱신. 만약 갱신된 거리가 더 짧다면 해당 정점의 최단 거리를 갱신.
  4. 모든 정점을 확정할 때까지 2번과 3번의 과정을 반복.

다익스트라 알고리즘을 JavaScript로 구현하기 위해서 우선순위 큐(Priority Queue)를 사용하여 효율적인 처리 구현

JavaScript 코드로 구현된 예시:

// 우선순위 큐 클래스 정의
class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(element, priority) {
    this.queue.push({ element, priority });
    this.sort();
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    return this.queue.shift().element;
  }

  sort() {
    this.queue.sort((a, b) => a.priority - b.priority);
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

// 다익스트라 알고리즘 함수
function dijkstra(graph, start) {
  const distances = {};
  const visited = {};
  const queue = new PriorityQueue();

  // 모든 정점의 최단 거리를 무한대로 초기화
  for (let vertex in graph) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;

  queue.enqueue(start, 0);

  while (!queue.isEmpty()) {
    const currentVertex = queue.dequeue();
    visited[currentVertex] = true;

    const neighbors = graph[currentVertex];

    for (let neighbor in neighbors) {
      const distance = distances[currentVertex] + neighbors[neighbor];

      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        queue.enqueue(neighbor, distance);
      }
    }
  }

  return distances;
}

// 그래프 정의
const graph = {
  A: { B: 5, C: 2 },
  B: { D: 1, E: 6 },
  C: { B: 1, D: 3 },
  D: { E: 1 },
  E: {},
};

const startVertex = "A";
const shortestDistances = dijkstra(graph, startVertex);

console.log(shortestDistances);

위의 코드에서는 PriorityQueue 클래스를 사용하여 우선순위 큐를 구현하고, dijkstra 함수를 통해 다익스트라 알고리즘을 구현. 그래프는 인접 객체 형태로 표현되며, 최단 거리를 저장하는 distances 객체와 방문 여부를 저장하는 visited 객체를 사용.

알고리즘이 종료되면 distances 객체에는 출발점으로부터 각 정점까지의 최단 거리가 저장되어 있다. 이를 통해 출발점으로부터 각 정점까지의 최단 경로를 찾는다