최단 경로 알고리즘
가장 짧은 경로를 찾는 알고리즘
•
다양한 문제 상황
◦
한 지점에서 다른 한 지점까지의 최단 경로
◦
한 지점에서 다른 모든 지점까지의 최단 경로
◦
모든 지점에서 다른 모든 지점까지의 최단 경로
•
각 지점은 그래프에서 노드로 표현
•
지점 간 연결된 도로는 그래프에서 간선으로 표현
다익스트라 알고리즘
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
•
음의 간선이 없을 때 정상적으로 동작
◦
현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음.
•
그리드 알고리즘으로 분류됨.
◦
매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
•
동작 과정
1.
출발 노드 설정
2.
최단 거리 테이블 초기화
3.
미방문 노드 중 최단 거리가 가장 짧은 노드 선택
4.
해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5.
3, 4번 과정 반복
•
알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음.
•
처리 과정에서 더 짧은 경로를 찾으면 해당 경로를 최단 경로로 갱신
다익스트라 알고리즘의 특징
•
그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정 반복
•
단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음.
◦
한 단계당 하나의 노드에 대한 최단 거리를 확정 짓는 것으로 이해 가능
•
알고리즘 수행 뒤 테이블에 각 노드까지의 최단 거리 정보가 저장됨.
◦
완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 함.
다익스트라 알고리즘의 간단한 구현 방법
•
단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)
python 코드
성능 분석
•
총 O(V)번 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 함.
→ 전체 시간 복잡도 O(V²)
•
노드 개수가 5000개 이하라면 이 코드로 가능하지만, 10000개일 때는?
우선순위 큐(Priority Queue)
우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료 구조
•
Python에서는 표준 라이브러리 형태로 지원
힙(Heap)
•
우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나
•
최소 힙(Min Heap)과 최대 힙(Max Heap)
•
다익스트라 최단 경로 알고리즘 포함 다양한 알고리즘에 사용
힙 라이브러리 사용 예제: 최소 힙
힙 라이브러리 사용 예제: 최대 힙
다익스트라 알고리즘의 개선된 구현 방법
•
단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조 사용
•
다익스트라 알고리즘 동작의 기본 원리는 동일
◦
현재 가장 가까운 노드를 저장하기 위해 힙 자료구조를 추가적으로 사용한다는 것만 다름
◦
현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙 사용
python 코드
성능 분석
•
노드를 하나씩 꺼내 검사하는 반복문(while문)은 노드의 개수 V 이상의 횟수로는 처리되지 않음.
→ 전체 시간 복잡도 O(ElogV)
플로이드 워셜 알고리즘
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
•
단계별로 거쳐 가는 모든 노드를 기준으로 알고리즘 수행
◦
매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정은 필요 X
•
2차원 테이블에 최단 거리 정보 저장
•
다이나믹 프로그래밍 유형에 속함.
•
각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인
◦
a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사
•
점화식
python 코드
