---

Shortest Path

가장 짧은 경로를 찾는 Algorithm

최단 경로(Shortest Path) Algorithm은 가장 짧은 경로를 찾는 알고리즘을 의미하며, 대표적으로 아래와 같은 문제 상황이 있다.

• 한 지점에서 다른 한 지점까지의 최단 경로
• 한 지점에서 다른 모든 지점까지의 최단 경로
• 모든 지점에서 다른 모든 지점까지의 최단 경로

이 때 각 지점은 그래프에서 노드, 지점 간 연결된 도로는 그래프에서 간선으로 표현한다.

---

Dijkstra

다익스트라(Dijkstra) 최단 경로 Algorithm은 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.

음의 간선이 없을 때 정상적으로 동작하며, 현실 세계의 도로(간선)는 음의 간선으로 표현되지 않는다.

또한 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류되기 때문에, 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.

Action Process

다익스트라 알고리즘의 동작 과정을 정리하면 다음과 같다.

[Step 1]. 출발 노드를 설정합니다.
[Step 2]. 최단 거리 테이블을 초기화한다.
[Step 3]. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
[Step 4]. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
[Step 5]. 위 과정에서 3번과 4번을 반복한다.

위 과정을 코드로 구현하면 다음과 같다.

const graph = [
  [Infinity, 1, Infinity, 2, Infinity],
  [1, Infinity, 3, Infinity, 2],
  [Infinity, 3, Infinity, Infinity, 1],
  [2, Infinity, Infinity, Infinity, 2],
  [Infinity, 2, 1, 2, Infinity],
];

// 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
const visited = Array(N).fill(false);
// 최단 거리 테이블 초기화
const dist = visited.map((_, i) => graph[0][i]);

// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
const findSmallestNode = (visited, distance) => {
  let minDist = Infinity;
  let minIdx = 0; // 가장 최단 거리가 짧은 노드(인덱스)
  
  for (let i = 0; i < distance.length; i++) {
    if (visited[i]) continue;
    if (distance[i] < minDist) {
      minDist = distance[i];
      minIdx = i;
    }
  }
  return minIdx;
};

const dijkstra = (graph, visited, dist) => {
  // 시작 노드에 대해서 초기화
  distance[0] = 0;
  visited[0] = true;
  
  // 시작 노드를 제외한 전체 노드에 대해 반복
  for (let i = 0; i < distance.length; i++) {
    // 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
    const nodeIdx = findSmallestNode(visited, distance);
    visited[nodeIdx] = true;

    // 현재 노드와 연결된 다른 노드를 확인
    for (let j = 0; j < distance.length; j++) {
      if (visited[j]) continue;
      
      // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
      if (distance[j] > distance[nodeIdx] + graph[nodeIdx][j])
        distance[j] = distance[nodeIdx] + graph[nodeIdx][j];
    }
  }
};

Time Complexity

위에서 구현한 다익스트라 Algorithm은 총 $O(V)$번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 한다.

따라서 전체 시간 복잡도는 $O(V^2)$가 되며, 이 때 $V$는 노드의 개수를 의미한다.

일반적으로 코딩 테스트의 최단 경로 문제는 전체 노드 개수가 5,000개 이하라면 위와 같은 코드로 문제를 해결할 수 있다.

하지만 노드의 개수가 10,000개를 넘어간다면 Priority Queue방식을 사용해 문제를 해결해야 한다.

---

Priority Queue

우선순위 큐(Priority Queue)는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선순위 큐를 이용할 수 있다.

Heap

힙(Heap)은 우선순위 큐를 구현하기 위해 사용되는 자료구조 중 하나이다.

종류에는 최소 힙(Min Heap), 최대 힙(Max Heap)이 있다.

• 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

힙은 다익스트라 최단 경로 알고리즘을 포함한 다양한 알고리즘에서 사용된다.

Action Process

우선순위 큐를 사용하여 구현한 다익스트라 Algorithm은 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용한다.

기본 동작 원리는 동일하지만, 현재 가장 가까운 노드를 저장해 놓기 위해 힙 자료구조를 추가적으로 이용한다는 점이 다르다.

현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙(Min Heap)을 사용

우선순위 큐를 사용한 다익스트라 알고리즘의 동작 과정을 정리하면 다음과 같다.

위 과정을 코드로 구현하면 다음과 같다.

// 0번 노드는 사용하지 않는 빈 노드이다.
// 이는 시작 노드를 1번으로 설정하기 위함이다.
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);
    }
  });
}

Time Complexity

힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 $O(ElogV)$이다.

노드를 하나씩 꺼내 검사하는 반복문(while문)은 노드의 개수 $V$ 이상의 횟수로는 처리되지 않는다.

결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수$(E)$만큼 연산이 수행될 수 있다.

직관적으로 전체 과정은 $E$ 개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.

---

Floyd-Warshall

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.

단, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.

그래서 플로이드 워셜 알고리즘은 2차원 테이블에 최단 거리 정보를 저장하며, 다이나믹 프로그래밍 유형에 속한다.

또한 각 단계마다 특정한 노드 $k$를 거쳐 가는 경우를 확인하므로, $a$에서 $b$로 가는 최단 거리보다 $a$에서 $k$를 거쳐 $b$로 가는 거리가 더 짧은지 검사한다.

이를 통해 점화식을 구하면 다음과 같다.

Action Process

플로이드 워셜 알고리즘의 동작 과정을 정리하면 다음과 같다.

위 과정을 코드로 구현하면 다음과 같다.

function floydWarshall(dist) {
  // 점화식에 따라 플로이드 워셜 알고리즘을 수행
  for (let k = 0; k < dist.length; k++) {
    for (let i = 0; i < dist.length; i++) {
      for (let j = 0; j < dist.length; j++) {
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
}

const graph = [
  [0, 3, 6, Infinity],
  [7, 0, 8, 4],
  [Infinity, Infinity, 0, 2],
  [Infinity, 9, Infinity, 0],
];

floydWarshall(graph);
console.log(graph);

Time Complexity

플로이드 워셜 알고리즘은 노드의 개수가 $N$개일 때 알고리즘상으로 $N$번의 단계를 수행한다.

각 단계마다 $O(N^2)$의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.

따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 $O(N^3)$이다.

---

참고 자료

(이코테 2021) 이것 취업을 위한 코딩 테스트다 - 동빈나