🏄♀️ 코딩테스트/🐍 Python
[ 이코테 강의 ] 최단 경로 알고리즘
Po_tta_tt0
2022. 4. 26. 12:37
반응형
최단 경로 문제
- 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미
- 문제 상황
- 한 지점에서 다른 한 지점가지의 최단 경로
- 한 지점에서 다른 모든 지점까지의 최단 경로
- 모든 지점에서 다른 모든 지점까지의 최단 경로
- 각 지점은 그래프에서 노드로 표현
- 지점 간 연결된 도로는 그래프에서 간선으로 표현
다익스트라 최단 경로 알고리즘 개요
- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상작동
- 형실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다
- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다
- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복
동작 과정
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 3-4번 반복
- 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다
- 처리 과정에서 더 짧은 경로를 찾으면 '이제부터는 이 경로가 가장 짧은 경로야' 하고 갱신한다
다익스트라 알고리즘의 특징
- 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택
- 단계를 거치며 한 번 처리된 최단 거리는 더 이상 바뀌지 않는다
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는다
- 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다
- 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 하긴 하지만 일반 코테에서는 잘 안나온다
우선순위 큐(Priority Queue)
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
- 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 이용할 수 있다
- 대부분의 프로그래래밍 언어에서 표준 라이브러리 형태로 지원된다
| 자료구조 | 추출되는 데이터 |
|---|---|
| 스택 | 가장 나중에 삽입된 데이터 |
| 큐 | 가장 먼저 삽입된 데이터 |
| 우선순위 큐 | 가장 우선순위가 높은 데이터 |
힙(Heap)
- 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나
- 최소 힙과 최대 힙이 있다
- 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다
| 우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| 리스트 | O(1) | O(N) |
| 힙 | O(logN) | O(logN) |
다익스트라 알고리즘 : 개선된 구현 방법
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조 이용
- 다익스트라 알고리즘이 동작하는 기본 원리는 동일
- 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용하기만 할 뿐
- 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용
- 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)
- 노드를 하나씩 꺼내 검사하는 반복문 while은 노드의 개수 V 이상의 횟수로는 처리되지 않는다
- 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수행될 수 있다.
- 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼는 연산과 매우 유사
- 시간 복잡도를 O(ElogE)로 표현할 수 있다
- 중복 간선을 포함하지 않는 경우에 이를 O(ElogV)로 정리할 수 있음.
- O(ElogE) => O(ElogV^2) => O(2ElogV) => O(ElogV)
- 노드의 개수가 10000개 이상이어도 대게 1초 안으로 구현 가능
플로이드 워셜 알고리즘 개요
- 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
- 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행
- 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다
- 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장
- 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다
- 시간복잡도는 O(N^3).. 그냥 다익스트라 쓰자..
- 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다
- a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사
- 점화식
Dab = min(Dab,Dak+Dkb)
플로이드 워셜 알고리즘 성능 분석
- 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행
- 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려
- 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)
반응형