최단경로 알고리즘

최단경로 알고리즘

- 말 그대로 가장 짧은 경로를 찾는 알고리즘

- 길찾기 문제라고도 불린다.

- 다양한 사례에 맞는 알고리즘이 각각 존재한다.

 

코딩 테스트에서 가장 많이 등장하는 유형인 다익스트라 알고리즘과 플로이드 워셜 알고리즘에 대해 정리하겠다.

 

다익스트라 알고리즘 Dijkstra

- 기본적으로 그리디 알고리즘이다.   why? 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복

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

- 그러나 음의 edge가 없을 때 정상적으로 동작한다는 것을 알아둬야 한다.

(현실 세계의 길은 음의 edge가 없기 때문에 다익스트라 알고리즘은 실제 GPS 소프트웨어의 기본 알고리즘이다.)

- 시간 복잡도는 O(E logV) / V는 노드의 수,  E는 edge의 수

 

1. 출발 노드 설정. 최단거리 테이블 초기화 

(최단거리를 구하는 것임으로 테이블을 무한대 값으로 갖도록 초기화하면 된다.)

2. 방문하지 않은 노드 중 최단거리인 노드를 선택한다.

3. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.

4. 2번과 3번을 반복한다.

-> 각 노드에 대한 현재 까지의 최단거리 정보를 항상 1차원 리스트에 저장하며 계속 갱신한다.

 

다익스트라 알고리즘은 힙 자료구조를 사용하면 탐색을 빠르게 해 수행시간을 줄일 수 있다.

 

힙(Heap)

- 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나.

- 우선순위 큐는 우선순위가 높은 데이터를 가장 먼저 삭제한다.

- 파이썬에는 PriorityQueue 또는 heapq가 있다. (heapq가 더 빠르다.) -> 최소 힙

- 최소 힙은 가장 값이 낮은 데이터를 먼저 삭제하고 최대 힙은 가장 값이 높은 데이터를 먼저 삭제한다.

- 최소 힙을 최대 힙으로 사용하고 싶으면 데이터를 넣을 때 음수 부호를 붙이면 된다.

 

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

- 기본적으로 다이나믹 프로그래밍이다.

- 모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해주는 알고리즘

- 모든 노드에 대해 다른 모든 노드로 가는 최단거리 정보를 담기 때문에 2차원 리스트가 필요하다.

- N번의 단계에서 매번 O(N^2)의 시간이 소요 -> 시간 복잡도 O(N^3)

플로이드 워셜 알고리즘 점화식