[알고리즘] 최단 경로 알고리즘

January 30, 2023 7 분 소요

최단 경로 (Shortest Path)

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 다른 말로 ‘(빠른) 길 찾기’ 문제라고도 불린다.

길 찾기 문제는 이미 상황에 맞는 효율적인 알고리즘들이 정립되어 있기 때문에, 코딩테스트를 준비하는 입장에서는 상황에 맞는 알고리즘을 신속하게 사용할 줄만 알면 될 것이다.

가장 대표적인 상황 두 가지는 다음과 같다.

한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우

이 때 지점이라 함은 그래프의 노드를 지칭하고, 지점간 연결된 도로 및 길은 간선으로 표현된다. 간선에 매겨진 숫자는 곧 해당 경로의 비용이 된다.

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

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

다익스트라 최단 경로 알고리즘은 ‘음의 간선’이 없을 때 정상적으로 동작하므로 주로 현실 세계의 길을 표현할 때 채택되어진다.

다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류 된다. 왜냐하면 매번 ‘가장 비용이 적은 노드’를 선택해서 임의의 과정을 반복하기 때문이다.

알고리즘의 기본 원리는 다음과 같다.

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

최단 거리 테이블은 ‘출발 노드에서 출발하여 각 노드에 도달하기 위한 현재까지의 최단 거리’를 나타내는 1차원 리스트이다.

즉 매번 현재 처리하고 있는 노드를 기준으로 주변 간선들을 확인 한 뒤에 현재까지의 경로 + 주변 간선 경로 가 최단 거리 테이블에 기록된 경로보다 더 짧으면 갱신해나가는 것을 모든 노드에 대하여 반복하는 것이다.

이 과정에서 노드를 선택할 때 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 확인해 선택하기 때문에 그리디 알고리즘으로 볼 수 있는 것이다.

이렇게 최단 거리가 가장 짧은 노드를 선택했을 때, 해당 노드는 ‘최단 거리’가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다. 즉 다익스트라 알고리즘이 진행되면서 한 단계당 하나의 노드(해당 단계에 선택된 노드)에 대한 최단 거리를 확실히 찾는 것으로 볼 수 있다.

다익스트라 알고리즘의 시간 복잡도는 O(V^2)이며, V는 노드의 개수를 의미한다. 각각의 노드에 모두 방문하여(V), 각 노드에서 지금까지 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하기 위해 순차 탐색(V)을 하기 때문이다.

다익스트라 최단 경로 알고리즘 구현 in 파이썬

import sys
input = sys.stdin.readline
INF = int(1e9) # 10억을 무한으로 설정

# n: 노드의 개수, m: 간선의 개수
n, m = map(int, input().split())
# start: 시작 노드 번호
start = int(input()) 

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

# 방문하지 않은 노드 중 가장 최단 거리가 짧은 노드 번호 반환
def get_smallest_node():
    min_value = INF
    index = 0
    # 순차 탐색
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    
    # 시작 노드를 제외하고 n - 1번 반복
    for i in range(n - 1):
        # now: 현재 반복에서 최단 거리가 가장 짧은 노드 번호
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:
            # cost: 현재 노드까지의 경로 + 각각의 간선 비용
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

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

앞서 말했듯이 다익스트라 최단 경로 알고리즘은 V개의 노드 모두에서 매번 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 탐색하기 위해 순차 탐색을 하므로 O(V^2)의 시간복잡도를 갖는다고 하였다.

따라서 최단 경로 문제를 풀 때 노드의 개수가 5,000개 이하라면 무리 없이 문제를 해결할 수 있겠지만, 10,000개를 넘어가게 되면 위 코드로는 문제를 해결하기가 어려울 수가 있다.

이렇게 노드의 개수 및 간선의 개수가 많을 때는 개선된 다익스트라 알고리즘을 이용해야 한다.

개선된 다익스트라 알고리즘

개선된 다익스트라 알고리즘은 최악의 경우에도 시간 복잡도 O(ElogV)를 보장하는 알고리즘이다.

다익스트라 알고리즘에 비해 개선된 부분은 바로 각각의 노드에서 ‘방문하지 않은 노드 중 최단 거리가 가장 짧은 노드’를 탐색하기 위해 순차 탐색을 했던 부분이다.

개선된 다익스트라 알고리즘은 해당 탐색 부분을 단순히 선형적으로 찾는 순차 탐색에서, 힙 자료구조를 사용한 우선순위 큐를 사용하여 로그 시간안에 다음 노드를 찾는 방법으로 개선하여 더욱 빠르게 다음 노드 탐색을 완료할 수 있다는 점이 특징이다.

자료구조 힙에 대한 자세한 설명은 추후에 포스팅하도록 하겠다.

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 큐에서 삭제한다는 점이 보통 큐와는 다르다. 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우 우선순위 큐를 사용한다.

대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리를 지원하기 때문에 별도로 우선순위 큐를 구현할 필요는 없다. 파이썬에서는 PriorityQueue 혹은 heapq를 사용할 수 있다.

우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용되며, 우선순위 큐에 데이터를 삽입할 때는 (우선순위, 값)으로 묶어서 삽입한다. 이렇게 삽입한 후 우선순위 큐에서 데이터를 꺼내게 되면 우선순위가 높은 데이터가 먼저 나오게 된다.

힙을 이용하여 우선순위 큐를 구현하게 되면 삽입과 삭제의 시간 복잡도가 모두 O(logN)이 된다.

개선된 다익스트라 알고리즘 구현 in 파이썬

그럼 우리는 이전 다익스트라 알고리즘에서 모든 노드 각각에서 최단 경로 노드를 탐색하기 위해 사용했던 get_smallest_node() 함수를 사용하지 않고 우선순위 큐를 이용하는 방식으로 대체하게 된다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 10억을 무한으로 설정

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    dijkstra(start)

    for i in range(1, n + 1):
        if distance[i] == INF:
            print("INFINITY")
        else:
            print(distance[i])

개선된 다익스트라 알고리즘의 시간 복잡도

개선된 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이다. 시간 복잡도가 위와 같이 나타나는 이유는, 위 코드에서 확인할 수 있듯이, distance[now] < dist와 같은 조건으로 인해 한 번 처리된 노드는 더 이상 처리되지 않는다. 따라서 노드를 하나씩 꺼내서 검사하는 반복문 while은 노드의 개수 V 이상의 횟수로는 반복되지 않는다.

또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인하게 되므로 결국 최대 간선의 개수 E만큼의 연산이 수행된다.

따라서 개선된 다익스트라 최단 경로 알고리즘은 E개의 원소를 우선순위 큐에 넣었다가 빼내는 연산과 매우 흡사하다. 힙에 N개의 데이터를 모두 넣고, 이후에 모두 빼는 연산은 O(NlogN)이라고 볼 수 있는데(N번 삽입 후 N번 삭제 = 2NlogN), 개선된 다익스트라 최단 경로 알고리즘은 E개의 원소를 다루므로 시간 복잡도는 O(ElogE)임을 알 수 있다.

이 때, E는 항상 V^2 보다 작다고 말할 수 있는데, 왜냐하면 모든 노드끼리 서로 다 연결되어있는 완전 연결 그래프에서 E는 V^2과 같다. 하지만 이는 가장 최대의 간선의 개수이므로, E는 항상 V^2보다 작다고 말할 수 있다.

따라서 logE는 logV^2보다 작으므로, 이때 logV^2는 2logV이고 이는 결국 O(logV)이다. 따라서 개선된 다익스트라 알고리즘의 전체 시간 복잡도를 간단히 O(ElogV)라고 볼 수 있다.

플로이드 워셜 알고리즘 (Floyd-Warshall)

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다.

플로이드 워셜 알고리즘 또한 다익스트라 알고리즘과 마찬가지로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다.

플로이드 워셜 알고리즘에서는 노드가 N개일 때 각 노드 N개에서 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.

다익스트라 알고리즘에서는 출발 노드가 1개이므로 출발 노드에서 다른 노드까지의 최단 경로를 저장하는 1차원 리스트를 사용한 반면, 플로이드 워셜 알고리즘에서는 모든 노드에서 다른 모든 노드까지의 최단 경로를 저장하기 위해 2차원 리스트를 사용한다.

또한 다익스트라 알고리즘은 그리디 알고리즘을 기본으로 사용한 반면 플로이드 워셜 알고리즘은 점화식에 맞게 2차원 리스트를 갱신하는 다이나믹 프로그래밍 방식을 사용한다는 특징이 있다.

플로이드 워셜 알고리즘에서는 각 노드에 방문했을 때 다른 모든 노드들이 해당 노드를 거쳐 지나가는 모든 경우를 고려한 뒤 최단 거리를 갱신한다.

예를 들면 현재 확인하고 있는 노드(1번 노드)를 제외하고, N-1개의 노드 중 서로 다른 노드 (A,B)쌍을 선택한 뒤 A > 1 > B로 가는 비용을 확인한 뒤 최단 거리를 갱신한다는 것이다.

이 때 N-1개의 노드 중 서로 다른 노드 (A, B)쌍을 찾는 경우의 수는 n-1P2이므로 O(N^2)이다. 이와 같은 과정을 N번 반복하기 때문에 O(N^3)의 시간 복잡도를 갖게 되는 것이다.

플로이드 워셜 알고리즘의 구체적인 점화식은 다음과 같다.

Dab = min(Dab, Dak + Dkb)

즉 A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신하는 것이다.

플로이드 워셜 알고리즘 구현 in 파이썬

파이썬으로 작성한 플로이드 워셜 알고리즘의 소스코드는 다음과 같다.

INF = int(1e9) # 무한

n = int(input())
m = int(input())
# INF로 채워진 n + 1개의 행과 열의 2차원 리스트 선언
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에게 가는 비용은 0
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력받아 초기화
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print("INF", end=" ")
        else:
            print(graph[a][b], end=" ")
    print() # 줄바꿈

References

이것이 취업을 위한 코딩테스트다 in 파이썬

Twitter Facebook LinkedIn

주노 정

[알고리즘] 최단 경로 알고리즘

최단 경로 (Shortest Path)

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

다익스트라 최단 경로 알고리즘 구현 in 파이썬

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

개선된 다익스트라 알고리즘

개선된 다익스트라 알고리즘 구현 in 파이썬

개선된 다익스트라 알고리즘의 시간 복잡도

플로이드 워셜 알고리즘 (Floyd-Warshall)

플로이드 워셜 알고리즘 구현 in 파이썬

References

공유하기

댓글남기기

참고

[TypeScript] 제네릭

[TypeScript] 클래스

[TypeScript] 인터페이스

[TypeScript] 타입스크립트의 함수