[Javascript 코테 대비] 최단 경로 찾기

최단 경로 (Shortest Path)

짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 한다.

최단 경로 알고리즘은 보통 그래프로 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다.

또한 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다.

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

그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

0보다 작은 값을 가지는 간선이 없을 때 정상적으로 동작한다.

기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.

알고리즘의 원리를 간략히 설명하면 다음과 같다.

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

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 배열에 저장하고 계속 갱신한다.

function dijkstra(start, graph) {
  	const INF = Number.Number.MAX_SAFE_INTEGER;
  
	const distance = [];
  	for(let i = 0; i < graph.length; i++) distance[i] = INF;
  
  	const heap = [];
  	heap.push([0, start]);
  	distance[start] = 0;
  
  	while(heap.length > 0) {
      	const dist, now = distance.shift();
      	if(distance[now] < dist) continue;
      	for(const i of graph[now]) {
        	const cost = dist + i[1];
          	if(cost < distance[i[0]]) {
            	distance[i[0]] = cost;
              	heap.push([cost, i[0]]);
              	heap.sort((a, b) => a[0]-b[0]);
            }
        }
    }
}

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.

단게마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다.

모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에 2차원 배열에 '최단 거리' 정보를 저장한다.

기본적으로 다이나믹 프로그래밍이라고 볼 수 있다.

function floyd_warshall(start, graph) {
  	const INF = Number.Number.MAX_SAFE_INTEGER;
  	
    const distance = [];
    for(let i = 0; i < graph.length; i++) {
      distance[i] = [];
      for(let j = 0; j < graph.length; j++) {
      	if(i === j) distance[i][j] = 0;
        else distance[i][j] = INF;
      }
    }
  	
  	for(let k = 0; k < graph.length; k++)
      for(let i = 0; i < graph.length; i++)
        for(let j = 0; j < graph.length; j++)
          graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
}