[Python] 최단경로를 위한 다익스트라(Dijkstra) 알고리즘

🔊 이번 포스팅에는 최근에 Python으로 알고리즘을 공부하기 시작하면서 알게 된 여러 알고리즘의 원리와 Python으로 구현하는 방법에 대해 소개해보려 한다. 필자는 최근 알고리즘 공부를 '나동빈'님의' '이것이 취업을 위한 코딩 테스트다 with 파이썬'이라는 책과 백준 온라인 저지 사이트로 하고 있다. 이 중 '나동빈'님이 저자이신 책에서 가르쳐주는 내용을 기반으로 배운 내용을 정리해보려 한다.

 

이번 포스팅에서는 최단 경로를 찾는 데 자주 사용되는 다익스트라(Dijkstra) 알고리즘 개념에 대해 알아보고 Python으로 구현하는 방법에 대해 알아보려고 한다.

 

최단경로는 어떻게 찾을까?

---

다익스트라 알고리즘은 최단 경로 알고리즘 종류 중 하나이다. 말 그대로 특정 지점에서 다른 특정 지점까지의 최단 경로를 구한다거나 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 문제이다. 보통 최단 경로 문제는 그래프를 이용해 표현하는데, 각 지점은 그래프에서 노드(vertex)로 표현되고 경로(거리)는 간선(edge)로 표현된다. 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다고 한다.

 

책에서 소개하는 최단 경로 알고리즘 종류는 다익스트라 최단경로 알고리즘, 플로이드 워셜 알고리즘이다. 이 중 다익스트라 알고리즘은 간단하게 구현하되 시간이 오래 걸리는 방법과 구현하기는 까다롭지만 시간이 빠르게 동작하는 방법 2가지를 소개한다. 이번 포스팅에서는 그 중에 동작의 원리를 이해하기 위한 목적과 동시에 기초적인 방법으로서 간단하게 구현하되 시간이 상대적으로 오래 걸리는 방법에 대해 알아본다.

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

다익스트라 알고리즘은 알고보면 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 자연스레 녹아들어 있다. 다익스트라 알고리즘은 그래프에서 여러 개의 노드가 존재할 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 보통 음의 간선이 존재하지 않는 즉, 간선(edge)의 값이 0 이상의 양수일 때 정상적으로 동작한다. 그래서 실제로 다익스트라 알고리즘은 GPS 소프트웨어의 기본 알고리즘으로 채택되고 있다고 한다.

 

다익스트라 최단 경로 알고리즘은 매번 가장 거리가 짧은 노드를 선택해서 임의의 횟수의 과정을 계속적으로 반복하게 된다. 알고리즘의 동작 원리를 단계화시키면 다음과 같다.

 

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화(그러므로 최단 거리를 기록할 테이블을 정의해야 함)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택(방문하지 않은 노드를 체크해야 하므로 이를 위한 테이블을 정의해야 함)
4. 해당 노드를 거쳐 다른 노드로 가는 간선 비용을 계산하여 최단 거리 테이블을 업데이트
5. 위 과정에서 3, 4번을 반복

위 단계에도 써있다시피 구현하기 위해 먼저 2가지의 빈 1차원 리스트를 정의해주어야 한다. 첫 번째는 최단 거리를 기록할 테이블이다. 이 리스트는 인덱스를 노드 번호로 하기 위해 N개의 노드가 있다고 가정할 때 N+1 길이로 하면서 원소값은 매우 큰 수를 넣어준다. 책에서는 10억(1e9)라는 숫자를 정의하지만 대부분의 문제에서는 주어지는 간선 정보를 1억(1e8) 미만의 값으로 정의해주기 때문에 1억의 값으로 넣어주어도 무방할 듯하다. 두 번째는 방문한 노드가 무엇인지 체크하기 위한 리스트이다. 이것도 마찬가지로 인덱스를 노드 번호로 하기 위해 N개의 노드가 있다고 할 때 N+1 길이로 하는 리스트를 정의해준다. 원소값은 문제에 따라 다르게 줄테지만 기본적으로는 False(방문하지 않음) 값으로 초기화시켜준다.

 

이제 구체적으로 다익스트라 알고리즘이 어떻게 동작하는지 살펴보자. 설명 자료는 참고한 책의 저자 나동빈님의 자료를 차용하였다.

1. 1번째 초기 단계

 

첫 번째 단계

 

시작노드가 빨간색인 1번 노드라고 가정하자. 그리고 아래에 표는 시작노드가 1번이라고 가정하고 1번 노드로부터 각 노드들 간의 거리를 표로 나타내었다. 그래서 최초에는 시작노드인 1번 노드에서 1번 노드로의 거리는 0이기 때문에 0으로 업데이트 해주고 나머지 값은 무한(매우 큰 수)로 초기화시켜준다.

2. 2번째 단계

이제 시작노드인 1번 노드로부터 도달할 수 있는 인접 노드들의 거리를 표에 갱신시켜준다. 아래와 같이 말이다.

 

두 번째 단계

3. 3번째 단계

이제 시작노드인 1번 노드를 방문처리 하고 1번 노드의 인접노드들 중 방문하지 않은 노드들(아직까진 1번 노드밖에 방문하지 않았으므로 2,3,4번 노드 모두 후보가 된다) 중 시작 노드인 1번 노드와 가장 최단거리인 4번 노드를 다음에 탐색할 노드로 선택한다. 참고로 하단의 자료에서 회색은 방문한 노드, 점선으로 된 간선은 이미 처리한 간선을 의미한다.

 

3번째 단계

 

이제 헷갈릴 수 있으니 주의를 기울여 잘 이해해보자. 먼저 탐색할 4번 노드는 3번, 5번과 간선으로 연결되어 있다. 먼저 3번에 대해 표를 갱신하는 부분을 살펴보자. $min(5, 1+3)$ 이라고 되어 있다. 여기서 5는 2번째 단계에서 갱신했던 시작노드 1번에서 3번 노드로 다이렉트로 한 번에 갈 수 있는 거리였다. 그리고 1+3 이라고 되어 있는 부분은 시작노드 1번에서 4번 노드로 가는 거리비용 1 과 4번 노드에서 3번 노드로 가는 거리비용 3을 의미한다. 이 중 거리비용을 최소화하는 경로는 시작노드인 1번에서 3번으로 다이렉트로 가는 것보다 4번 노드를 거쳐 3번 노드로 가는 즉, 1 -> 4 -> 3 으로 가는 경로가 최단 경로가 된다. 이런 방식으로 동일하게 4번노드의 인접노드인 5번 노드도 갱신해준다.(참고로 5번 노드는 2번째 단계에서 시작노드인 1번과 연결되어 있지 않아서 무한대값이였기 때문에 당연히 4번노드를 통해 가는 것이 최단 경로이다)

 

자, 이제 다익스트라 알고리즘을 거의 다 이해한 것이나 마찬가지이다. 다음에 탐색할 노드를 선정해보자. 가장 마지막으로 갱신된 거리 테이블 기준으로 방문하지 않은 노드들 중 가장 거리가 작은 즉, 원소값이 가장 작은 인덱스 번호를 다음으로 탐색할 노드로 선정한다. 위 예시에서는 2번 5번이 거리 비용이 2로 동일한데, 이 때는 노드 번호가 작은 순서대로 먼저 탐색하는 걸로 한다.

4. 4번째 단계

 

4번째 단계

 

2번 노드도 똑같이 도달할 수 있는 간선으로 연결되어 있는 인접노드인 3,4번 노드에 대한 간선 비용을 위와 같이 갱신시켜준다. 그리고 방문하지 않은 노드 중 갱신한 테이블 기준으로 시작노드와 가장 최단거리인 5번 노드를 탐색한다. 이런식으로 모든 노드를 한 번씩 탐색하여 다익스트라 알고리즘 과정을 최종적으로 완료한다.

 

결국 다익스트라 알고리즘은 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정을 반복하는 게 핵심이다. 그런데 여기서 자세히 살펴보면, 각 단계마다 탐색노드로 한 번 선택된 노드는 최단거리가 갱신되고 난 후 재갱신되지 않는 것을 확인할 수 있다. 해당 포스팅에서는 다익스트라 알고리즘이 완전 다 종료된 후의 갱신된 거리 테이블을 첨부하지는 않았지만 책 속 자료나 기타 자료를 살펴보면 한 번 갱신된 최단 거리는 이후 단계를 거치더라도 더 작은 거리 값으로 갱신되지 않는 것을 볼 수 있다. 또 마지막 노드에 대해서는 해당 노드를 거쳐 다른 노드로 가는 경우를 확인할 필요가 없다. 

2. 간단한 다익스트라 알고리즘을 Python으로 구현하기

간단한 다익스트라 알고리즘은 $V$가 노드의 개수라고 가정할 때, 시간 복잡도가 $O(V^2)$이게 된다. 왜냐하면 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 거리 테이블의 길이(=노드의 개수) 만큼 순차탐색을 수행하기 때문이다. 결과적으로 순차탐색이라는 것 때문에 주어지는 데이터가 만약 10,000개를 넘어가는 경우라면 시간 복잡도에서 문제가 발생한다. 그래서 이 포스팅 이후로 개선된 다익스트라 알고리즘에 대해 배울 예정이다. 

 

간단한 다익스트라 알고리즘을 Python으로 구현하는 코드는 다음과 같다. 저자 동빈님은 이 코드 뿐만 아니라 추후에 소개될 개선된 다익스트라 알고리즘을 자다가도 벌떡 일어나서 바로 구현할 수 있어야 할 정도로 반복 숙지를 권장하는 만큼 해당 코드를 1일 1회 쳐보는 걸로 계속 연습해보자.

 

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
# 주어지는 그래프 정보 담는 N개 길이의 리스트
graph = [[] for _ 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 not visited[i] and distance[i] < min_value:
            min_value = distance[i]
            index = i
    return index

# 다익스트라 알고리즘
def dijkstra(start):
    # 시작노드 -> 시작노드 거리 계산 및 방문처리
    distance[start] = 0
    visited[start] = True
    # 시작노드의 인접한 노드들에 대해 최단거리 계산
    for i in graph[start]:
        distance[i[0]] = i[1]

    # 시작노드 제외한 n-1개의 다른 노드들 처리
    for _ in range(n-1):
        now = get_smallest_node()  # 방문X 면서 시작노드와 최단거리인 노드 반환
        visited[now] = True        # 해당 노드 방문처리
        # 해당 노드의 인접한 노드들 간의 거리 계산
        for next in graph[now]:
            cost = distance[now] + next[1]  # 시작->now 거리 + now->now의 인접노드 거리
            if cost < distance[next[0]]:    # cost < 시작->now의 인접노드 다이렉트 거리
                distance[next[0]] = cost


dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print('도달 할 수 없음')
    else:
        print(distance[i])