최단 경로

송현준·2022년 12월 9일

알고리즘 자료구조 책정리

알고리즘, 자료구조

목록 보기

9/12

가장 빠른 길 찾기

최단 경로

가장 짧은 경로를 찾는 알고리즘
최단 경로 문제는 보통 그래프를 이용해표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다.
그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다.

다익스트라 최단 경로 알고리즘

그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다.
음의 간선이란 0보다 작은 값을 가지는 간선을 의미
매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘으로 분류된다.
'각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.

알고리즘의 간략한 원리

출발 노드를 설정한다.
최단 거리 테이블을 초기화한다.
방문하지 않은노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
위 과정에서 3과 4번을 반복한다.

구현 방법 2가지

방법 1. 구현하기 쉽지만 느리게 동작하는 코드
방법 2. 구현하기에 조금 더 까다롭지만 빠르게동작하는 코드

방법 1. 간단한 다익스트라 알고리즘

$O(V^2)$ 의 시간 복잡도
여기서 V는 노드의 개수를 의미
처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언
이후에 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.
간단한 다익스트라 알고리즘 소스코드
5000개 이하라면 일반적으로 이 코드로 문제를 풀 수 있을 것
하지만 노드의 개수가 10,000개를 넘어가는 문제라면 이코드로는 해결하기 어렵다.

방법 2. 개선된 다익스트라 알고리즘

$O(ElogV)$ 시간 복잡도
여기서 V는 노드의 개수이고, E는 간선의 개수를 의미한다.
개선된 다익스트라 알고리즘에서는 힙(Heap)자료구조를 사용한다.
특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.

힙 설명

힙 자료구조는 우선순위큐를 구현하기 위하여 사용하는 자료구조 중 하나다.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다
스택, 큐, 우선순위 큐 자료구조 비교

자료구조 추출되는 데이터
스택(Stack) 가장 나중에 삽입된 데이터
큐(Queue) 가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터
우선순위 큐를 구현할 때는 내부적으로 최소 힙 혹은 최대 힙을 이용한다.
최소 힙을 이용하는 경우 '값이 낮은 데이터가 먼저 삭제' 되며, 최대 힙을 이용하는 경우 '값이 큰 데이터가 먼저 삭제'된다.
파이썬 라이브러리는 기본적으로 최소 힙 구조를 이용하는데 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소 힙 구조를 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.
구현 방식에 따른 시간 복잡도

우선순위 큐 구현 방식 삽입 시간 삭제 시간
리스트 $O(1)$ $O(N)$
힙(Heap) $O(logN)$ $O(logN)$
힙을 이용하는 경우 모든 원소를 저장한 뒤에 우선순위에 맞게 빠르게 뽑아낼 수 있으므로 힙은 '우선순위 큐'를 구현하는데 가장 많이 사용된다
우선순위 큐를 적용한 다익스트라 알고리즘은 최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)는 전과 동일하게 이용하고, 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용한다.
개선된 다익스트라 알고리즘 소스코드

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	$O(1)$	$O(N)$
힙(Heap)	$O(logN)$	$O(logN)$

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘
단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다.
매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다.
2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다.
모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문
플로이드 워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다.
노드의 개수가 N이라고 할 때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문
점화식
$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$
- 'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신하겠다는 것
- 즉, '바로 이동하는 거리'가 '특정한 노드를 거쳐서 이동하는 거리'보다 더 많은 비용을 가진다면 이를 더 짧은 것으로 갱신한다는 것
$O(N^3)$ 시간 복잡도
플로이드 워셜 알고리즘 소스코드