[javascript] 최단 경로 알고리즘

18 Dec 2023

javascript

최단 경로 알고리즘은 그래프에서 두 노드 간의 최단 경로를 찾는 알고리즘입니다. 그래프는 노드와 이를 연결하는 에지로 구성되며, 각 에지는 가중치를 가지고 있을 수 있습니다. 최단 경로 문제는 가중 그래프에서 두 노드 간의 최단 경로와 그 가중치를 찾는 문제입니다. 다양한 최단 경로 알고리즘들이 개발되었는데, 여기서는 가장 유명한 두 가지 알고리즘에 대해 알아보겠습니다.

다익스트라 알고리즘

다익스트라 알고리즘은 음수 가중치를 허용하지 않는 가중 그래프에서 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 출발 노드에서 각 노드로의 최단 경로를 차례대로 찾아나가는 방식으로 동작합니다. 다익스트라 알고리즘은 그리디 알고리즘(Greedy Algorithm)으로 분류되며, 매 단계마다 현재까지 발견된 최단 경로를 가진 노드를 선택하여 최단 경로를 갱신합니다.

다음은 JavaScript를 사용한 다익스트라 알고리즘의 간단한 구현입니다:

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

  let unvisited = new Set(Object.keys(graph));
  let previousNodes = {};

  while (unvisited.size > 0) {
    let currentNode = getClosestNode(unvisited, distances);
    unvisited.delete(currentNode);

    for (let neighbor in graph[currentNode]) {
      let distance = distances[currentNode] + graph[currentNode][neighbor];
      if (distance < distances[neighbor]) {
        distances[neighbor] = distance;
        previousNodes[neighbor] = currentNode;
      }
    }
  }
  return distances;
}

function getClosestNode(unvisited, distances) {
  return Array.from(unvisited).reduce((minNode, node) =>
    distances[node] < distances[minNode] ? node : minNode
  );
}

벨만-포드 알고리즘

벨만-포드 알고리즘은 음수 가중치를 허용하는 그래프에서 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 최단 경로를 찾는 데에 반복적인 계산을 사용하며, 모든 가능한 경로를 연구하는 다이나믹 프로그래밍 알고리즘입니다.

다음은 JavaScript를 사용한 벨만-포드 알고리즘의 간단한 구현입니다:

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

  for (let i = 0; i < Object.keys(graph).length - 1; i++) {
    for (let node in graph) {
      for (let neighbor in graph[node]) {
        if (distances[node] + graph[node][neighbor] < distances[neighbor]) {
          distances[neighbor] = distances[node] + graph[node][neighbor];
        }
      }
    }
  }
  return distances;
}

결론

최단 경로 알고리즘은 다양한 분야에서 활용되고 있으며, 다익스트라 알고리즘과 벨만-포드 알고리즘은 이러한 문제를 해결하는 데에 널리 사용되는 알고리즘입니다. 알고리즘 선택은 문제의 특성에 따라 달라질 수 있으며, 여러 상황에 맞는 적절한 알고리즘을 선택하는 것이 중요합니다.