[Javascript로 정리하는 이코테] 8. 최단 경로

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

개념

• 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘
• 보통 그래프를 이용해 표현한다.
• 대표적인 최단 거리 알고리즘으로는 다음 3가지가 있다.
  • 다익스트라 알고리즘
  • 플로이드 워셜 알고리즘
  • 벨만 포드 알고리즘

 

다익스트라 알고리즘

• 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 음의 간선이 없을 때 정상적으로 동작한다.

 

동작 원리

1. 출발 노드 설정
2. 최단 거리 테이블 초기화 (1차원 배열)
   • 연결된 간선 → 그 값
   • 연결되지 않은 간선 → 무한
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드에서 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 모든 노드에 대해 3, 4번 반복

 

각 노드에 대한 현재까지의 최단 거리 정보를 1차원 배열에 저장하며 배열을 계속 갱신한다는 특징이 있으며, 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다는 점에서 그리디 알고리즘의 유형으로 볼 수 있다.

 

 

예제 9-1. 간단한 다익스트라 알고리즘

• 3번 과정을 순차 탐색으로 수행한다.
• 시간복잡도: O(n)

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, s, ...rest] = input;
const [n, m] = nm.split(' ').map((v) => +v);
const start = +s;
const arr = rest.map((str) => str.split(' ').map((v) => +v));

let visited = [...Array(n + 1).fill(false)];
let d = [...Array(n + 1).fill(Infinity)];

function solution(n, m, start, arr) {
  //초기화
  const graph = Array.from(Array(n + 1), () => []);
  for (const v of arr) {
    const [a, b, c] = v;
    graph[a].push([b, c]);
  }

  //방문하지 않은 노드에서 최단 거리가 가장 짧은 노드의 인덱스 반환
  const getSmallestNode = () => {
    let min = Infinity;
    let index = 0;
    for (const i in d) {
      if (!visited[i] && min > d[i]) {
        min = d[i];
        index = i;
      }
    }
    return index;
  };

  const dijkstra = (start) => {
    //시작 노드 초기화
    d[start] = 0;
    visited[start] = true;
    for (const i of graph[start]) {
      const [node, cost] = i;
      d[node] = cost;
    }

    //시작 노드를 제외한 전체 노드에 대해 반복
    for (let i = 0; i < n; i++) {
      const cur = +getSmallestNode();
      visited[cur] = true;

      for (const j of graph[cur]) {
        const node = j[0];
        const cost = d[cur] + j[1];
        if (cost < d[node]) {
          d[node] = cost;
        }
      }
    }
  };

  dijkstra(start);

  for (let i = 1; i <= n; i++) {
    if (d[i] === Infinity) {
      console.log('INFINITY');
    } else {
      console.log(d[i]);
    }
  }

  return d;
}

console.log(solution(n, m, start, arr));

한 번 선택된(방문한) 노드는 최단 거리가 감소하지 않는다(갱신되지 않는다). 즉, 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.

 

 

예제 9-2. 개선된 다익스트라 알고리즘

• 3번 과정을 이진 탐색으로 수행한다.
  • 최소 힙으로 구현한 우선순위 큐를 활용한다.
• 별도의 방문 처리 변수 visited가 필요 없다.
• 시간복잡도: O(nlogm)

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, s, ...rest] = input;
const [n, m] = nm.split(' ').map((v) => +v);
const start = +s;
const arr = rest.map((str) => str.split(' ').map((v) => +v));

let d = [...Array(n + 1).fill(Infinity)];

function solution(n, m, start, arr) {
  const graph = Array.from(Array(n + 1), () => []);
  for (const v of arr) {
    const [a, b, c] = v;
    graph[a].push([b, c]);
  }

  const dijkstra = (start) => {
    //시작 노드 초기화
    const pq = new PriorityQueue();
    pq.push([0, start]); //[거리, 노드]
    d[start] = 0;

    while (!pq.empty()) {
      const [dist, cur] = pq.pop(); //현재 최단 거리가 가장 짧은 노드

      //최단 거리가 아닌 경우(방문한 적이 있는 경우) 스킵
      if (d[cur] < dist) continue;

      for (const i of graph[cur]) { //인접 노드 탐색
        const node = i[0];
        const cost = dist + i[1];
        if (cost < d[node]) {
          pq.push([cost, node]);
          d[node] = cost;
        }
      }
    }
  };

  dijkstra(start);

  for (let i = 1; i <= n; i++) {
    if (d[i] === Infinity) {
      console.log('INFINITY');
    } else {
      console.log(d[i]);
    }
  }

  return d;
}

console.log(solution(n, m, start, arr));

 

우선순위 큐 구현 (최소힙)

• 자바스크립트의 경우 우선순위 큐를 직접 구현해야 한다.

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  empty() {
    return this.heap.length === 0;
  }

  peek() {
    return this.heap[0];
  }

  push(data) {
    this.heap.push(data);

    let i = this.heap.length - 1;
    while (i > 0) {
      const parent = ~~((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }

  pop() {
    if (this.empty()) return;

    const value = this.peek();
    [this.heap[0], this.heap[this.heap.length - 1]] = [
      this.heap[this.heap.length - 1],
      this.heap[0],
    ];
    this.heap.pop();
    this._heapify();
    return value;
  }

  _heapify() {
    const x = this.peek();
    const n = this.heap.length;
    let cur = 0;

    while (2 * cur + 1 < n) {
      const leftChild = 2 * cur + 1;
      const rightChild = leftChild + 1;
      const smallerChild =
        rightChild < n && this.heap[rightChild] < this.heap[leftChild]
          ? rightChild
          : leftChild;

      //루트 노드의 값이 더 큰 경우 swap
      if (x > this.heap[smallerChild]) {
        [this.heap[cur], this.heap[smallerChild]] = [
          this.heap[smallerChild],
          this.heap[cur],
        ];
        cur = smallerChild;
      } else {
        break;
      }
    }
  }
}

const pq = new PriorityQueue();
pq.push(3);
pq.push(5);
pq.push(2);
pq.pop();
pq.push(6);
pq.push(1);
pq.pop();

while (!pq.empty()) {
  console.log(pq.pop());
}

 

플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘
• 시간복잡도: O(n^3)

 

동작 원리

1. 최단 거리 테이블 초기화 (2차원 배열)
   • 연결된 간선 → 그 값
   • 연결되지 않은 간선 → 무한
2. i에서 j로 갈 때, k를 거쳐 가는 것이 더 빠르다면 최단 거리 갱신
   • D[i][j] = min(D[i][j], D[i][k] + D[k][j])
3. 모든 노드에 대해 2번 반복

 

단계마다 거쳐 가는 노드를 기준으로 최단 거리 정보를 담은 2차원 배열을 갱신해 나아간다. 노드의 개수가 N일 때, N번만큼의 단계를 반복하면서 점화식에 맞게 2차원 리스트를 갱신하기 때문에 다이나믹 프로그래밍의 유형으로 볼 수 있다.

 

 

예제 9-3. 플로이드 워셜 알고리즘

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [n, m, ...rest] = input;
(n = +n), (m = +m);
const arr = rest.map((str) => str.split(' ').map((v) => +v));

function solution(n, m, arr) {
	//최단 거리 테이블 초기화
	let d = Array.from(Array(n + 1), () => Array(n + 1).fill(Infinity));
  for (let i = 1; i <= n; i++) d[i][i] = 0;
  for (const value of arr) {
    const [u, v, cost] = value;
    d[u][v] = cost;
  }

	//모든 노드에 대해 반복
	for (let k = 1; k <= n; k++) {
		//최단 거리 갱신
    for (let from = 1; from <= n; from++) {
      for (let to = 1; to <= n; to++) {
        if (k === from || from === to) continue; //생략 가능
        d[from][to] = Math.min(d[from][to], d[from][k] + d[k][to]);
      }
    }
  }

  let ans = '';
  for (let from = 1; from <= n; from++) {
    for (let to = 1; to <= n; to++) {
      if (d[from][to] === Infinity) ans += 'INFINITY';
      else ans += `${d[from][to]} `;
    }
    ans += '\n';
  }

  return ans;
}

console.log(solution(n, m, arr));

 

 

실전 문제

미래 도시

• 플로이드 워셜 알고리즘
• 1 → K → X를 가는 최단 경로를 구하는 문제로, 1에서 K까지 가는 최단 경로와 K에서 X까지 가는 최단 경로를 각각 알아야 하기 때문

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nm, ...arr] = input;
const [n, m] = nm.split(' ').map((v) => +v);
let [x, k] = arr[m].split(' ').map((v) => +v);
arr.pop();
arr = arr.map((str) => str.split(' ').map((v) => +v));

function solution(n, m, x, k, arr) {
  const d = Array.from(Array(n + 1), () => Array(n + 1).fill(Infinity));
  for (let i = 1; i <= n; i++) d[i][i] = 0;
  for (const value of arr) {
    const [u, v] = value;
    d[u][v] = 1;
    d[v][u] = 1;
  }

  for (let i = 1; i <= n; i++) {
    for (let from = 1; from <= n; from++) {
      for (let to = 1; to <= n; to++) {
        if (i === from || from === to) continue;
        d[from][to] = Math.min(d[from][to], d[from][i] + d[i][to]);
      }
    }
  }

  const dist = d[1][k] + d[k][x];
  return dist >= Infinity ? -1 : dist;
}

console.log(solution(n, m, x, k, arr));

 

전보

• 다익스트라 알고리즘
• 출발지 C에서 다른 도시들로 가는 최단 경로를 구해야 하기 때문

const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');

let [nmc, ...arr] = input;
const [n, m, c] = nmc.split(' ').map((v) => +v);
arr = arr.map((str) => str.split(' ').map((v) => +v));

let d = [...Array(n + 1).fill(Infinity)];
function solution(n, m, c, arr) {
  let graph = Array.from(Array(n + 1), () => []);
  for (const value of arr) {
    const [u, v, dist] = value;
    graph[u].push([v, dist]);
  }

  const pq = new PriorityQueue();
  pq.push([0, c]);
  d[c] = 0;

  while (!pq.empty()) {
    const [dist, cur] = pq.pop();

    if (d[cur] < dist) continue;

    for (const i of graph[cur]) {
      const node = i[0];
      const cost = dist + i[1];
      if (cost < d[node]) {
        pq.push([cost, node]);
        d[node] = cost;
      }
    }
  }

  d = d.slice(1);
  const count = d.filter((v) => v && v !== Infinity).length;
  const max = Math.max(...d);

  return [count, max];
}

console.log(solution(n, m, c, arr));