🌿 다익스트라 알고리즘 (최단경로 알고리즘)

경로 상 가장 짧은 경로를 찾는 최단경로 알고리즘은 그래프의 가중치 여부, 가중치의 범위에 따라 사용해야 하는 알고리즘이 달라진다.

보통 가중치가 없는 경우는 BFS, 가중치가 양수일 경우 다익스트라, 가중치가 음수일 경우 벨만-포드를 사용한다.

이 포스트에서는 다익스트라 알고리즘을 정리한다.

🌿 다익스트라(Dijkstra) 알고리즘

• 다익스트라 최단경로 알고리즘은 특정한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다.
• 이 때 가중치는 반드시 음수가 아니어야 한다.
• 참고로 데이크스트라가 원래 맞는 표현이라고 한다.

🌿 동작 원리

동작 원리는 출발 노드를 기준으로 비용이 적은 노드를 선택하고, 그 노드를 거쳐 다른 노드로 가는 경로를 최소 비용으로 업데이트 하는 것이다.

1. 출발 노드 설정
2. 최단 거리 테이블을 초기화 (모든 거리의 초기값이 무한대라고 가정)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블 갱신
5. 3, 4의 과정 반복

위의 과정을 그림으로 알아보자
먼저 총 6개의 노드가 있고 각 노드 사이의 비용이 위와 같다고 정의하자
이 때 최단거리 테이블은 시작노드인 1번 노드를 제외하고 무한대로 정의한다.
1번 노드는 시작 노드이기 때문에 0으로 초기화 해준다. (1번에서 1번으로 가는 비용은 0이기 때문)

그 후 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택해야 한다.
현재 모든 노드를 방문하지 않았고 그 중 최단거리가 가장 짧은 노드인 1번 노드를 선택한다.
그 후 1번 노드와 연결된 2번, 3번, 4번노드의 최단 거리를 처리해준다.

• 2번노드가 1번노드를 거쳐가면 0+2의 비용이 들고, 1번노드를 거치지 않는다면 현재 값인 무한이 된다. 최단 거리 테이블은 더 작은 값인 2로 갱신된다.
• 3번노드가 1번노드를 거쳐가면 0+5의 비용이 들고, 1번노드를 거치지 않는다면 현재 값인 무한이 된다. 최단 거리 테이블은 더 작은 값인 5로 갱신된다.
• 4번노드가 1번노드를 거쳐가면 0+1의 비용이 들고, 1번노드를 거치지 않는다면 현재 값인 무한이 된다. 최단 거리 테이블은 더 작은 값인 1로 갱신된다.

다음도 마찬가지로 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택해야 한다.
방문한 1번 노드를 제외한 노드 중 최단거리가 가장 짧은 노드인 4번 노드를 선택한다.
그 후 4번 노드와 연결된 3번, 5번노드의 최단 거리를 처리해준다.

• 3번노드가 4번노드를 거쳐가면 1+3의 비용이 들고, 4번노드를 거치지 않는다면 현재 값인 5가 된다. 최단 거리 테이블은 더 작은 값인 4로 갱신된다.
• 5번노드가 4번노드를 거쳐가면 1+1의 비용이 들고, 4번노드를 거치지 않는다면 현재 값인 무한이 된다. 최단 거리 테이블은 더 작은 값인 2로 갱신된다.

다음도 마찬가지로 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택해야 한다.
방문한 1번, 4번 노드를 제외한 노드 중 최단거리가 가장 짧은 노드는 2번노드와 5번노드가 있다.
둘 중 아무거나 먼저 처리해도 상관 없지만 보통 노드 번호가 작은 노드를 택한다.
따라서 2번 노드를 선택하고, 2번노드와 연결된 3번, 4번노드를 처리해준다.

• 3번노드가 2번노드를 거쳐가면 2+3의 비용이 들고, 2번노드를 거치지 않는다면 현재 값인 4가 된다. 최단 거리 테이블은 더 작은 값인 4로 갱신된다. (사실상 유지)
• 4번노드가 2번노드를 거쳐가면 2+2의 비용이 들고, 2번노드를 거치지 않는다면 현재 값인 1이 된다. 최단 거리 테이블은 더 작은 값인 1로 갱신된다. (사실상 유지)

다음도 마찬가지로 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택해야 한다.
방문한 1번, 4번, 2번 노드를 제외한 노드 중 최단거리가 가장 짧은 노드인 5번노드를 선택한다.
그 후 5번 노드와 연결된 3번, 6번노드의 최단 거리를 처리해준다.

• 3번노드가 5번노드를 거쳐가면 2+1의 비용이 들고, 5번노드를 거치지 않는다면 현재 값인 4가 된다. 최단 거리 테이블은 더 작은 값인 3으로 갱신된다.
• 6번노드가 5번노드를 거쳐가면 2+2의 비용이 들고, 5번노드를 거치지 않는다면 현재 값인 무한이 된다. 최단 거리 테이블은 더 작은 값인 4로 갱신된다.

다음도 마찬가지로 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택해야 한다.
방문한 1번, 4번, 2번, 5번 노드를 제외한 노드 중 최단거리가 가장 짧은 노드인 3번노드를 선택한다.
그 후 3번 노드와 연결된 2번, 6번노드의 최단 거리를 처리해준다.

• 2번노드가 3번노드를 거쳐가면 3+3의 비용이 들고, 3번노드를 거치지 않는다면 현재 값인 2가 된다. 최단 거리 테이블은 더 작은 값인 2로 갱신된다. (사실상 유지)
• 6번노드가 3번노드를 거쳐가면 3+5의 비용이 들고, 3번노드를 거치지 않는다면 현재 값인 6이 된다. 최단 거리 테이블은 더 작은 값인 6으로 갱신된다. (사실상 유지)

마지막으로 방문하지 않은 노드인 6번 노드를 선택한다.
6번 노드를 통해 갈 수 있는 노드가 없기 때문에 반복은 종료된다.

이렇게 특정노드인 1번노드에서 모든 노드로 가는 최단거리를 갱신할 수 있다.
사실생 모든 경로를 탐색하고 현재 기준 가장 최소 비용을 소모하는 노드를 선택하기 때문에 그리디 알고리즘에 포함되기도 하고, 최단거리 배열을 갱신해 나가는 과정에서 DP 알고리즘에 포함되기도 한다.

🌿 소스코드(JS)

// 노드의 개수, 그래프, 정점/간선/가중치 정보
const n = 6;
const graph = Array.from({ length: n + 1 }, () => []);
const inputs = ['1 2 2', '1 3 5', '1 4 1', '2 3 3', '2 4 2', '3 2 3', '3 6 5', '4 3 3', '4 5 1', '5 3 1', '5 6 2']

// 정점/간선/가중치 정보를 숫자값으로 파싱하여 그래프에 저장해준다.
for (const input of inputs) {
  const [s, e, c] = input.split(' ').map(Number);
  
  graph[s].push([e, c]);
}

// 최단거리 테이블중 최단거리를 가진 노드번호를 리턴하는 함수
const getMinNode = (distances, visited) => {
  let minDistance = Infinity;
  let minNode = -1;

  for (let i = 1; i <= n; i++) {
    if (!visited[i] && distances[i] < minDistance) {
      minDistance = distances[i];
      minNode = i;
    }
  }

  return minNode;
};

// 다익스드라 함수 구현
const dijkstra = (startNode) => {
  // 최단거리를 기록할 distance 배열, 방문 여부를 기록할 visited배열
  const distances = Array(n + 1).fill(Infinity);
  const visited = Array(n + 1).fill(false);
  
  // 시작노드의 최단 거리는 0
  distances[startNode] = 0;
 
  // 모든 노드를 탐색하며 최단거리 테이블을 갱신한다.
  // 무한반복이 아닌 for문을 사용해도 된다 한 번 방문한 노드는 다시 방문하지 않으니까
  while (true) {
    const node = getMinNode(distances, visited);
    
    // -1을 리턴받았다는 것은 방문안한 노드중에 최단노드가 발견되지 않았다는 것
    // 즉 모든 노드를 방문한 경우 종료한다.
    if (node === -1) break;
    visited[node] = true;
	
    // 최단경로 갱신
    for (const [v, w] of graph[node]) {
      if (distances[node] + w < distances[v]) {
        distances[v] = distances[node] + w;
      }
    }
  }

  return distances;
};

// 1번 노드부터 다른 모든 노드까지의 최단거리 테이블을 리턴한다.
dijkstra(1);

🌿 개선된 다익스트라?

그림으로 설명된 내용을 코드로 구현해봤다.
현재 코드에서는 최단 거리 테이블에서 다음 탐색 노드를 선택할 때, 아래와 같이 getMinNode와 같은 함수를 사용해 매번 모든 노드를 탐색한다.

const getMinNode = (distances, visited) => {
  let minDistance = Infinity;
  let minNode = -1;

  for (let i = 1; i <= n; i++) {
    if (!visited[i] && distances[i] < minDistance) {
      minDistance = distances[i];
      minNode = i;
    }
  }

  return minNode;
};

또한 방문 여부를 추적하기 위해 visited 배열이 필요하다.
이 방식은 추가적인 메모리가 필요하고, 최단 거리 노드를 선택하는 함수 내부에서 n번의 반복, 모든 노드에서 테이블을 갱신하는데 n번의 반복을 하기 때문에 O(n^2)의 시간복잡도를 가지게 된다.

우선순위큐(힙)을 사용해 구현하면 위 과정을 O(nlogn) 의 시간복잡도로 최적화 할 수 있다.

다만 자바스크립트는 우선순위 큐 자료구조를 지원하지 않아 직접 구현해야 한다.
가끔 코딩테스트 제한언어로 JavaScript만 두는 경우가 있는데 이 때는 우선순위 큐를 사용하는 문제가 나오지 않을 것이라 생각한다. 따라서 이 포스트에서 다루지 않는다.

이와 별개로 우선순위 큐를 직접 구현해보는 것은 자료구조를 이해하는 데 큰 도움이 되기 때문에 추후 별도로 포스팅을 할 예정이다!

🌿 Ref

• 이것이 취업을 위한 코딩테스트다
• [이것이 코딩 테스트다 with Python] 30강 다익스트라 최단 경로 알고리즘