Shortest Path Algorithm
길 찾기 문제라고도 불리는 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다.
한 지점에서 다른 지점까지의 최단 경로를 구하는 다익스트라 알고리즘과 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 플로이드 와샬 알고리즘에 대해 알아보자.
Dijkstra Algorithm
다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해준다. 음의 간선이 없을 때 정상적으로 동작하며, 매 순간 가장 비용이 적은 노드를 선택하는 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다. 원리는 다음과 같다.
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 3과 4 반복
책에서는 다익스트라 알고리즘 구현 방법을 2가지로 나눴다.
- 구현하기 쉽지만 느리게 동작하는 코드
- 구현하기 조금 까다롭지만 빠르게 동작하는 코드
전체 노드의 개수가 5,000개 이하인 최단 경로 문제라면 첫 번째 방법으로도 충분히 풀 수 있다. 하지만 노드의 개수가 10,000개를 넘어가면 두 번째 방법으로 해결해야 한다. 최단 경로 알고리즘을 응용하여 풀 수 있는 고난이도 문제가 많기 때문에 두 번째 방법을 정확히 이해하고 구현할 수 있어야 한다.
방법 1
위에서 언급했듯이 각 노드에 대한 최단 거리를 담는 1차원 리스트(최단 거리 테이블)를 선언한다. 그리고 단계마다 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 최단 거리 테이블을 순차 탐색한다.
그렇기 때문에 시간복잡도는 O(V^2) 로 다소 오래 걸린다.
방법 2
우선순위 큐를 구현하기 위해 힙 자료구조를 사용한다. heapq 라이브러리는 최소 힙을 기반으로 하기 때문에 거리가 짧은 노드 순서대로 큐에서 나오도록 작성하면 된다.
우선순위 큐를 이용하기 때문에 거리가 가장 짧은 노드를 선택하기 위해 단지 큐에서 노드를 꺼내면 된다. 그래서 최단 거리 테이블을 매 순간마다 탐색하는 첫 번째 방법과 달리 시간복잡도는 O(ElogV) 로 훨씬 빠르다.
Floyd-Warshall Algorithm
다익스트라 알고리즘은 한 지점에서 다른 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 알고리즘이다. 그렇다면 모든 지점에서의 최단 경로를 구해야 하는 경우는 어떡할까?
그럴 때 사용하는 것이 바로 플로이드 워셜 알고리즘이다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문에 최단 거리 테이블로 2차원 리스트를 이용한다.
노드의 개수만큼 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신하기 때문에 다이나믹 프로그래밍으로도 볼 수 있다.
플로이드 워셜 알고리즘은 각 단계에서 해당 노드를 거쳐 가는 경우를 고려한다. 예를 들어 1번 노드에 대해 확인할 경우 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려하면 된다. A → 1번 노드 → B처럼 말이다.
즉, A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신하는 것이 플로이드 워셜 알고리즘의 핵심이다.
참고
- 이것이 취업을 위한 코딩 테스트다