javascript - 다익스트라 알고리즘

다익스트라 알고리즘

네트워크에서 최단 경로를 찾는 알고리즘이며, 이 알고리즘은 엣지 가중치의 합이 최소가 되는 경로를 찾아줍니다. 즉, 그래프의 한 정점에서 다른 정점으로 가는 가장 짧은 경로를 찾는 문제를 해결하는데 사용됩니다.

 

1. 초기화: 시작 노드의 거리를 0으로, 나머지 모든 노드의 거리를 무한대로 설정합니다. 시작 노드를 현재 노드로 설정합니다.

2. 현재 노드에서 인접한 노드들의 거리를 계산합니다. 이 때, 기존에 설정한 거리보다 새로 계산한 거리가 짧으면 거리 정보를 업데이트합니다.

3. 모든 인접 노드에 대해 거리를 업데이트한 후에는 방문하지 않은 노드 중 거리가 가장 짧은 노드를 새로운 '현재 노드'로 설정합니다.

4. 모든 노드를 방문할 때까지 이 과정을 반복합니다.

 

다음과 같은 그래프를 가정하겠습니다.

  A -1- B -2- D
  |     |     |
  4     3     5
  |     |     |
  C -2- E -3- F

각 노드는 알파벳으로 표현하고, 엣지는 숫자로 가중치를 나타냈습니다.

다음은 Javascript로 구현한 다익스트라 알고리즘입니다.

const INFINITY = Number.MAX_SAFE_INTEGER;

const graph = {
  A: { B: 1, C: 4 },
  B: { A: 1, D: 2, E: 3 },
  C: { A: 4, E: 2 },
  D: { B: 2, F: 5 },
  E: { B: 3, C: 2, F: 3 },
  F: { D: 5, E: 3 },
};

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

  for (let node of unvisitedNodes) {
    distances[node] = INFINITY;
  }
  distances[start] = 0;

  while (unvisitedNodes.length > 0) {
    unvisitedNodes.sort((a, b) => distances[a] - distances[b]);

    let closestNode = unvisitedNodes.shift();

    for (let neighbor in graph[closestNode]) {
      let possiblePath = distances[closestNode] + graph[closestNode][neighbor];
      if (possiblePath < distances[neighbor]) {
        distances[neighbor] = possiblePath;
        predecessors[neighbor] = closestNode;
      }
    }
    visited[closestNode] = true;
  }

  return { distances, predecessors };
}

console.log(dijkstra(graph, 'A'));

이 코드는 시작 노드 A에서 다른 노드까지의 최단 경로와 거리를 계산합니다. 마지막 줄에서 dijkstra(graph, 'A') 함수를 호출하여 그 결과를 출력하고 있습니다. 출력 결과는 각 노드까지의 최단 거리(distances)와 그 최단 경로를 이루는 노드들의 선행자(predecessors)를 담고 있습니다.