최단거리를 구해보자 - 다익스트라 알고리즘

다익스트라 알고리즘은 최단거리를 찾는 대표적인 알고리즘이다.

노드끼리 거리값이 주어지고, 지정한 노드부터 다른 노드까지 갈 수 있는 거리를 수정해가면서 최단거리를 구한다.

 

순차탐색으로 구하느 방법과 우선순위 큐로 구하는 방법이 있는데

나는 우선순위 큐가 더 쉬운 것 같다.

 

const graph = [
  [], // 사용X
  [
    { to: 2, dist: 1 },
    { to: 4, dist: 2 },
  ],
  [
    { to: 1, dist: 1 },
    { to: 3, dist: 3 },
    { to: 5, dist: 2 },
  ],
  [
    { to: 2, dist: 3 },
    { to: 5, dist: 1 },
  ],
  [
    { to: 1, dist: 2 },
    { to: 5, dist: 2 },
  ],
  [
    { to: 2, dist: 2 },
    { to: 3, dist: 1 },
    { to: 4, dist: 2 },
  ],
];

// 1번 노드와 각 노드까지 최단 경로를 저장하는 배열 생성
const dist = Array(graph.length).fill(Infinity);

// 큐 생성 및 1번 노드에 대한 정보 저장
const queue = [{ to: 1, dist: 0 }];

// 1번 노드의 거리는 0 으로 설정
dist[1] = 0;

// 큐가 빌 때까지 반복
while (queue.length) {
  // 큐에서 방문할 노드 꺼내기
  const { to } = queue.pop();

  // 방문한 노드까지 이동한 거리 + 다음 방문 노드까지 거리를
  // 기존에 저장된 값과 비교해서 갱신
  graph[to].forEach((next) => {
    const acc = dist[to] + next.dist;
    if (dist[next.to] > acc) {
      dist[next.to] = acc;
      // 최단 경로가 되는 노드는 큐에 추가
      queue.push(next);
    }
  });
}

코드를 살펴보면 dist가 거리를 구하는 배열이다.

처음에는 infinity로 배열을 가득 채운다.

그리고 시작지점인 1번 노드에 길이 0짜리 오브젝트배열을 queue로 할당한다.

dist[1] 1번노드까지 거리는 자기 자신이므로 0이다.

 

while문을 통해 최단거리를 구한다.

const {to} = queue.pop은 자바스크립트 문법인데 queue에서 pop으로 꺼낸 to key값을 가진 value가 할당된다.

그러면 to는 처음에 입력했던 {to : 1, dist : 0}에서 1이 된다.

그리고 graph[1]을 forEach로 순회하면서 거리값이 dist에 있는 node번호 value보다 작으면 해당 값을 dist[node번호]에 넣어준뒤 queue에 push해준다.

 

이처럼 모든 graph를 순회하고 queue에 남는 값이 없으면

dist배열은 1번 노드를 기준으로 각 노드로 향하는 최단거리가 할당된다.

 

블로그에 써진 글과 소스코드를 가져왔는데 이해하는데 큰 도움이 됐다. 아래 링크에 더욱 자세한 설명이 있으니 참고하시길!

https://han-joon-hyeok.github.io/posts/dijkstra-algorithm/

다익스트라 알고리즘 개념 정리 및 구현 (JavaScript)