JavaScript로 이해하는 최적 경로 탐색 (최소 비용 경로, 다익스트라 알고리즘)

최적 경로 탐색이란?

"최적 경로 탐색"은 출발 지점에서 도착 지점까지 가는 여러 경로 중에서 "가장 비용이 적은 경로"를 찾는 과정을 의미합니다. 이때의 비용은 거리, 시간, 금액 등 다양한 기준이 될 수 있습니다. 실생활에서는 다음과 같은 곳에서 활용됩니다:

• 지도 앱: 최단 거리나 최소 소요 시간 경로 탐색
• 네트워크 라우팅: 패킷이 지나가는 효율적인 경로 계산
• 게임 개발: AI 캐릭터가 장애물을 피해 목표 지점까지 이동하는 경로

이러한 문제들은 그래프 이론의 한 부분이며, 여러 알고리즘 중 "다익스트라 알고리즘(Dijkstra's Algorithm)"이 가장 널리 쓰입니다.

---

다익스트라 알고리즘 개념 이해

"다익스트라 알고리즘"은 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최소 비용 경로를 계산하는 방법입니다. 이 알고리즘은 다음과 같은 개념에 기반합니다:

• 그래프: 노드(Vertex)와 간선(Edge)으로 구성
• 가중치: 간선을 지날 때의 비용 (예: 거리, 시간 등)
• 최단 거리 배열: 시작 노드에서 각 노드까지의 최소 비용을 저장
• 방문 여부: 어떤 노드가 이미 처리되었는지 여부를 확인

---

JavaScript로 구현하기 (배열 기반, 우선순위 큐 없음)

다익스트라 알고리즘은 원래 우선순위 큐를 활용하면 더 빠르지만, 이 글에서는 초보자도 이해하기 쉬운 배열 기반 방식으로 설명합니다.

예제 그래프 구조 (인접 리스트 기반)

const graph = {
  A: [{ node: 'B', cost: 2 }, { node: 'C', cost: 5 }],
  B: [{ node: 'A', cost: 2 }, { node: 'C', cost: 3 }, { node: 'D', cost: 1 }],
  C: [{ node: 'A', cost: 5 }, { node: 'B', cost: 3 }, { node: 'D', cost: 2 }],
  D: [{ node: 'B', cost: 1 }, { node: 'C', cost: 2 }]
};

다익스트라 알고리즘 구현

function dijkstra(graph, start) {
  const distances = {};
  const visited = {};
  const nodes = Object.keys(graph);

  // 초기화: 모든 노드의 거리를 무한대로, 시작 노드는 0으로
  for (const node of nodes) {
    distances[node] = Infinity;
  }
  distances[start] = 0;

  while (nodes.length > 0) {
    // 아직 방문하지 않은 노드 중 가장 거리가 짧은 노드 선택
    let minNode = null;
    for (const node of nodes) {
      if (!minNode || distances[node] < distances[minNode]) {
        minNode = node;
      }
    }

    const currentDistance = distances[minNode];
    const neighbors = graph[minNode];

    // 인접 노드들의 거리 계산
    for (const neighbor of neighbors) {
      const { node: nextNode, cost } = neighbor;
      const newDistance = currentDistance + cost;
      if (newDistance < distances[nextNode]) {
        distances[nextNode] = newDistance; // 더 짧은 거리로 갱신
      }
    }

    // 현재 노드를 방문 처리하고 리스트에서 제거
    visited[minNode] = true;
    nodes.splice(nodes.indexOf(minNode), 1);
  }

  return distances;
}

const result = dijkstra(graph, 'A');
console.log(result); // 각 노드까지의 최소 비용 출력

---

시간 복잡도 및 주의 사항

• 시간 복잡도: O(V^2) (V는 노드 개수)
  • 이 구현은 우선순위 큐를 사용하지 않아 효율이 떨어집니다.
  • heap을 이용하면 O((V + E) log V)까지 향상 가능
• 주의점:
  • 음의 가중치가 있는 그래프에는 사용할 수 없습니다.
  • 출발점이 여러 개인 경우에는 별도로 계산하거나 알고리즘을 확장해야 합니다.

---

마무리 및 추천 자료

다익스트라 알고리즘은 가장 기본적이면서도 강력한 경로 탐색 알고리즘입니다. 위와 같은 기본 구현을 학습한 후에는, 우선순위 큐를 이용한 개선 방법, A* 알고리즘과의 비교 등도 함께 공부해보는 것이 좋습니다.

추가 학습에 유용한 자료를 소개합니다:

• Visualgo - 다익스트라 시각화
• freeCodeCamp - Graph Algorithms
• replit - JavaScript 실습 환경