[Algorithm] 최단경로 알고리즘 with Python(다익스트라, 플루이드워셜)
코딩테스트에서 활용될 수 있는 최단 경로 그래프 알고리즘에 대해서 간단히 정리했다.
이전에 작성한 [Algorithm] 코딩테스트 대비 Cheat Sheet 에서 탐색(BFS, DFS) 등의 기본적인 그래프 형태 데이터의 탐색 방법을 포함해 그리디, 다이나믹 프로그래밍 등에 정리했고, 본 글에서는 상대적으로 좀 더 난이도 있는 문제에 사용되는 최단 경로 그래프 알고리즘에 대해서 정리해보고자 한다.
최단 경로 알고리즘은 그래프 형태의 데이터에 대한 이해에 더해서 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘에 대한 이해를 필요로 한다.
List
최단 경로 알고리즘
- 다익스트라(Dijkstra) 알고리즘
- 플루이드 워셜(Floyd-Warshall Algorithm) 알고리즘
최단 경로(shortest Path) 알고리즘
최단 경로 알고리즘은 가장 짧은 경로를 찾는 길 찾기 알고리즘이다.
보통 그래프로 표현하며 각 지점은 그래프에서 ‘노드(Node)'로 표현되고, 지점간 연결된 도로는 그래프에서 ‘간선(edge)'으로 표현된다.
아래에서 알아볼 다익스트라 알고리즘와 플루이드 워셜 알고리즘은 모두 최단거리를 구하는 알고리즘이지만 목적이 조금 다르다. 다익스트라 알고리즘은 한 노드에서 다른 특정 노드까지의 최단 거리를 구하기 위한 알고리즘이고, 플루이드 워셜 알고리즘은 모든 노드에서 모든 노드까지의 최단 거리를 구하기 위한 알고리즘이다.
다익스트라(Dijkstra) 알고리즘
특정한 노드에서 출발하여 다른 노드로 가는 최단 경로를 구하기 위한 알고리즘이다. 0보다 작은 값을 가지는 ‘음의 간선'이 없어야 정상적으로 동작한다. 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되기도 한다.
다익스트라 최단 경로 알고리즘은 매번 ‘가장 비용이 적은 노드'의 선택을 반복하므로, 그리디 알고리즘의 일종으로 분류될 수 있다.
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드를 가는 비용을 계산하여 최단 거리 테이블 갱신
- 위의 3, 4 반복
다익스트라는 ‘각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.
다익스트라는 상대적으로 간단하지만 시간복잡도 O(N²)을 가진 방식, 또는 조금 더 복잡하지만 시간복잡도 O(ElogV)를 가진 방식, 두가지로 풀 수 있다. 여기서는 후자의 방식에 대해서만 정리했다.
시간복잡도 O(ElogV)를 가진 다익스트라 알고리즘을 구현하기 위해서는 힙(Heap) 자료구조의 활용을 필요로 한다. 힙 자료구조를 사용하게 되면 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 빠르게 찾을 수 있다. 이 노드를 찾는 탐색 과정에서 선형 시간이 아닌 로그 시간이 걸리므로 시간복잡도를 절약할 수 있다.
Heap
잠깐 힙에 대해서 간단히 살펴보자. 힙은 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나다. 스택은 LIFO, 큐는 FIFO의 특징을 갖는데, 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 꺼내는 점이 특징이다.
우선순위 큐를 구현할 때는 내부적으로 최소 힙(Min Heap) 또는 최대 힙(Max Heap)을 이용한다. 최소 힙을 이용하는 경우 값이 낮은 데이터가 먼저 삭제되며, 최대 힙을 이용하는 경우 값이 큰 데이터가 먼저 삭제된다. 언어별로 최소, 최대 힙 구현방식이 다를 수 있는데 파이썬 라이브러리는 기본적으로 최소 힙, C++는 최대 힙, 자바는 최소 힙을 이용하여 구현되어 있다.
최소 힙을 최대 힙처럼 사용하기 위해서는 값에 음수 부호(-)를 붙여서 사용할 수 있다.
최단 거리가 가장 짧은 노드를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식의 다익스트라 알고리즘 코드의 샘플이다.
플루이드 워셜(Floyd-Warshall Algorithm) 알고리즘
플루이드 워셜 알고리즘은 모든 지점에서 모든 지점으로의 최단 경로를 모두 구하는 경우에 활용할 수 있는 알고리즘이다.
노드의 개수가 N개일 때 N번의 단계를 수행하며, 단계마다 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담기 위한 2차원 리스트를 생성하는 O(N²)의 연산을 한다. 따라서 N번의 단계마다 O(N²)의 연산을 필요로 하는 이 알고리즘의 총시간 복잡도는 O(N³)이다.
이 알고리즘의 핵심인 점화식은 :
즉, i에서 j로 가는 비용과 k를 거쳐 j로 가는 비용을 비교하여 최소 비용으로 갱신하는 것이다. 여기서 k = N을 모두 순회하며, 가장 짧은 (i, j) 경로를 찾아서 갱신한다.
위의 그림에서 k=0으로 레이블된 첫번째 재귀에는 단일 edge로 직접 연결된 path들의 거리를 계산한다.
k=1에서는 정점 1을 거쳐가는 path들을 찾는다. 여기서는 path [2,1,3]이 여기서 찾아졌고, 기존의 path [2,3]을 대체한다. [2,3]은 더 적은 수의 edge를 지나지만 weight의 합은 더 크다.
k=2에서는 정점 {1, 2}를 거쳐가는 루트를 찾는다. 빨간색, 파란색 박스는 path [4,2,1,3]이 이전에 찾아진 두개의 path의 조합으로 이루어진 것을 설명한다.
k=3에서는 정점 {1, 2, 3}을 찾는 루트를 찾는다. 마지막으로 k=4에서 모든 가장 짧은 루트들을 찾는다.
k별 반복에서 찾은 거리를 매트릭스에 표현하면 아래와 같다. 각 k 반복별로 업데이트된 숫자는 진하게 표시되었다.
노드가 총 4개이므로 k=4, 즉 스텝 4까지 수행하였다.
소스 코드는 아래와 같다. 시간복잡도는 O(N³)이다.
Reference
나동빈, 이 것이 코딩테스트다(2020), 한빛미디어
