Search

최단 경로 알고리즘

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘
다양한 문제 상황
한 지점에서 다른 한 지점까지의 최단 경로
한 지점에서 다른 모든 지점까지의 최단 경로
모든 지점에서 다른 모든 지점까지의 최단 경로
각 지점은 그래프에서 노드로 표현
지점 간 연결된 도로는 그래프에서 간선으로 표현

다익스트라 알고리즘

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
음의 간선이 없을 때 정상적으로 동작
현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음.
그리드 알고리즘으로 분류됨.
매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
동작 과정
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 코드

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.