최단 경로 알고리즘

최단 경로 알고리즘이란

• 길 찾기 문제로, 가장 짧은 경로를 찾는 알고리즘. 주어진 문제를 노드, 간선 개념이 나오는 그래프로 나타내고 그래프 탐색을 통해 최단 경로를 찾는다.

• 그리디 알고리즘 또는 다이나믹 프로그래밍이 적용된다.

• 크게 3가지 있다, 다익스트라, 플로이드-워셜, 벨만포드→ 상황에 맞는 효율적인 알고리즘이 정해져 있다.

1. 다익스트라 알고리즘

• 한 정점에서 다른 특정 정점으로 가는 최단 경로를 구하는 알고리즘
• V개의 정점과 음수가 아닌 E개의 간선을 가진 그래프 G에서 특정 출발 정점(S)에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘

• 음의 간선(가중치가 0보다 작은 간선)이 없어야 한다.

• 그리디 알고리즘으로 분류된다.
• 탐욕적으로 최선의 선택, 즉 최소 비용만을 뽑아 탐색을 진행하기 때문

• 총 V*V번 연산이 필요하다. 따라서 O(V^2)의 시간복잡도를 가진다.

• 우선순위큐(힙 자료구조)를 사용하면 시간복잡도는 O(ElogV)로 개선된다.

• 사용 예시: 네비게이션 길 찾기(가장 가까운 주유소 위치), gps

탐색 과정

구현

class PriorityQueue {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }
  dequeue() {
    return this.values.shift();
  }
  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
	size() {
		return this.values.length - 1
	}
}

const dijkstra = (start, graph, V) => {
  const minHeap = new PriorityQueue();
  const dist = Array(V + 1).fill(Infinity);
  dist[start] = 0;
  minHeap.enqueue([start, 0]);

  while (minHeap.size()) {
    const [vertex, cost] = minHeap.dequeue();

    if (dist[vertex] < cost) continue;

    for (let i = 0; i < graph[vertex].length; i++) {
      const [nextVertex, nextCost] = graph[vertex][i];

      if (dist[nextVertex] > cost + nextCost) {
        dist[nextVertex] = cost + nextCost;
        minHeap.enqueue([nextVertex, dist[nextVertex]]);
      }
    }
  }

  return dist;
};

2. 플로이드워셜 알고리즘

• 모든 정점에서 다른 모든 정점까지 최단 경로를 구하는 알고리즘

• 각각의 노드에 대해 나머지 모든 노드로 가는 최단 거리 정보를 저장하기 위해 2차원 배열 사용
• 다익스트라의 경우 1차원 배열을 사용

• 다이나믹 프로그래밍으로 분류된다.
• 노드가 N개 일 때, N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신한다.
• N번의 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려합니다.

• 시간복잡도: O(N^3)

• 구현이 쉽고 모든 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 것이 장점이다.

• 노드의 개수가 적은 경우 플로이드워셜을 사용할 수 있지만, 노드의 개수가 많은 경우 우선순위큐를 사용하는 다익스트라가 훨씬 유리하다.

• 사용예시: 각 프롱이들의 위치에서 다른 프롱이들의 위치까지의 정보를 구하기

탐색 과정

1. 노드와 간선을 확인하고 최단 거리 테이블 생성한다.
• 이동할 수 없는 경로는 무한대로 입력하고, 자기 자신에서 자기 자신으로 가는 비용은 0으로 설정한다.

2. 1번 노드부터 시작, 1번 노드를 거쳐 가는 경우를 고려하여 최단 거리를 갱신한다.
• 현재 확인하고 있는 노드를 제외하고, N-1개의 노드 중 서로 다른 노드 (A,B)쌍을 선택하여,
A -> B 비용보다 A -> 1번 노드 -> B로 가는 비용이 더 작다면 최단 거리 갱신

3. 나머지 모든 노드에 대하여 똑같은 로직을 수행한다.

구현

const floydWarshall = (graph) => {
  const N = graph.length;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      for (let k = 0; k < N; k++) {
        if (graph[j][k] > graph[j][i] + graph[i][k]) {
					// i번을 경유해서 가는 경우의 비용이 더 작으면 갱신
          graph[j][k] = graph[j][i] + graph[i][k];
        }
      }
    }
  }
};

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

floydWarshall(graph);
console.log(graph);
// [
//   [ 0, 5, 11, 8 ],
//   [ 7, 0, 9, 13 ],
//   [ 2, 7, 0, 4 ],
//   [ 5, 10, 3, 0 ]
// ]

3. 벨만 포드 알고리즘

• 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
• V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다.
• 정점 하나씩 매 단계마다 모든 간선을 전부 확인하면서 모든 정점 간의 최단 거리를 구해나간다. 

• 음의 간선(가중치가 음수인 경우)도 가능하다.
• 다익스트라는 음의 간선은 불가능.

• 음의 사이클 존재 여부를 확인할 수 있다.
음의 사이클 찾는 방법
• V까지 반복하는 것이 아닌 한 번 더 해당 과정을 반복하는 겁니다. 음수사이클이 없을 경우에는 V+1 반복한다고 Dist 배열의 값들이 갱신되지 않습니다. 이유는 이론상 V정점들의 간선을 다 탐색했을 경우 각 정점들의 최단거리는 항상 구해지게 되어있기 때문이죠. 그러나 이 상태에서 한 번 더 반복했을 때 업데이트되는 경우는 음수사이클이 존재하여 Dist의 특정값에 - 가중치를 더해주는 경우겠죠. 그래서 V+1번째 탐색을 수행한 뒤 업데이트 되는 값의 존재여부를 발견하는 것은 음수사이클이 존재한다는 것을 알려주는 단서가 됩니다.

• 다익스트라 알고리즘이 모든 가중치가 양수인 경우에만 사용할 수 있는 반면에 벨만-포드 알고리즘은 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다. 다만 시간 복잡도는 벨만-포드가 더 크기 때문에 가중치가 모두 양수라면 굳이 벨만-포드를 사용할 필요가 없다.

• 시간 복잡도 O(VE)로 느리다.
• 다익스트라는 O(ElogV) 

• 사용 예시: 네트워크에서는 간선의 비용이 음수가 될 수 없으나 라우팅 테이블의 크기가 적고, 간단하기 때문에 소규모 네트워크에서 사용되는 거리 벡터 라우팅 프로토콜에 사용된다.

탐색 과정

1. 시작 노드를 설정한다.

2. 시작 노드에서 각 다른 노드의 거리 값을 무한대로 설정하고 시작 노드를 0으로 설정한다.

3. 현재 노드의 모든 인접 노드를 탐색하며 기존에 저장된 인접 노드까지의 거리보다 현재 노드를 거치고 인접 노드에 도달하는 게 더 짧을 경우 값을 갱신한다.

4. 3의 과정을 모든 노드에 대해 수행한다.

5. 모든 노드에 3 - 4를 수행하고서 또 거리가 갱신된다면 −∞를 발생시키는 음수 사이클이 존재함을 의미한다.

const bellmanFord = (start, edges, n, m) => {
  const INF = Infinity;
  const dist = Array.from(Array(v + 1), () => INF);
  dist[start] = 0;

	// 간선 개수(V)만큼 반복, 이미 start는 확인했으니 반복+1 => (총 반복횟수 V + 1)
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
			// 각 정점마다 모든 간선들을 탐색
      const curNode = edges[j][0];
      const nextNode = edges[j][1];
      const cost = edges[j][2];

      if (dist[curNode] != INF && dist[nextNode] > dist[curNode] + cost) {
				//(기존 인접 정점까지의 거리 > 기존 현재 정점까지 거리 + 현재 정점부터 인접 정점까지 거리)인 경우 갱신
        dist[nextNode] = dist[curNode] + cost;

        if (i == n - 1) {
          // n 번째 라운드에서도 값이 갱신되면 음수 순환이 존재하는 경우
          console.log('음수 사이클 존재');
					return
        }
      }
    }
  }

  // 0번 노드에서 다른 모든 노드로 가기 위한 최단 거리 출력
  for (let i = 0; i < v; i++) {
    if (dist[i] == INF) {
      console.log(-1);
    } else {
      console.log(i, dist[i]);
    }
  }
};

const v = 5;
const e = 8;
const edges = [
  [0, 1, -1],
  [0, 2, 4],
  [1, 2, 3],
  [1, 3, 2],
  [1, 4, 2],
  [3, 2, 5],
  [3, 1, 1],
  [4, 3, -3],
];

bellmanFord(0, edges, v, e);

// Vertex Distance
// 0 0
// 1 -1
// 2 2
// 3 -2
// 4 1