[Python] 최단 경로 알고리즘, Dijkstra 알고리즘

참고자료
[1] https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

[2] 이것이 코딩테스트다 with 파이썬

다익스트라 알고리즘이란?

다익스트라 알고리즘은 최단 경로 문제를 푸는데, 다이나믹 프로그래밍을 활용하는 알고리즘이다. 이는, 하나의 최단 거리를 구하기 위해 그 이전까지 구한 최단 거리 정보를 그대로 사용한다는 것이다.

다익스트라 알고리즘의 개요

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

다익스트라 알고리즘의 예시

실제 그림을 보면서 어떻게 처리되는 알고리즘인지 보자.

다음 그림과 같은 상황이 주어졌을 때, 1번에서 각 지점까지 이동하는데 드는 최소 비용을 알아보고자 한다.

출발점은, 당연히 비용 0이고, 우선 출발점에서 바로 이동이 가능한 2번, 3번의 비용을 기록하자.

이제, 방문하지 않은 노드 중 가장 비용이 저렴한 노드는 2번이다.

2번으로 이동하여 2번에서는 4, 5를 갈 수 있다. 비용을 갱신해주자.

 

비용을 갱신해 준 후, 4번에서는 3번과 5번을 갈 수 있을 것이다.

그런데 3번으로 가는 비용은 기존에 4번으로 간 최소 비용 5원 + 추가 이용 3원보다는, 앞에서 본 7원이 더 싸므로 비용을 갱신하지 않는다, 5번도 마찬가지로 추가 비용 갱신은 없다. 따라서, 4번은 방문처리만 하고 그 다음 비용이 저렴한 5번을 확인한다. 이 뒤로도 비용 갱신은 일어나지 않는다.  (더 저렴할 경우에는 갱신이 된다..)

따라서, 최저 비용은 다음과 같다.

 

다익스트라 알고리즘의 구현

쉽게 구현하는 버전은, 매 단계마다 진짜로 방문하지 않은 노드에서 최단거리가 가장 짧은 노드를 선택하는 것이다.

이때의 시간 복잡도는 O(V^2)이 된다. 노드의 개수가 많아지면, 문제의 해결은 어려울 것이다.

# 노드의 개수, 간선의 개수를 입력받는다.
n, m = map(int, input().split())
# 시작 노드
start = int(input())
# 노드 정보
graph = [[] for _ in range(n+1)]
# 방문 정보
visited = [False] * (n+1)
# 최단거리
distance = [INF] * (n+1)

# a번 노드에서 b번 노드로 가는 비용은 c다를 입력.
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

# 미방문 노드 중 최단거리를 짧은 노드의 번호를 반환
# 그런데, 이걸 List로 짜야 할까? Heap으로는?
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 = get_smallest_node()
        visited[now] = True
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐 가는 길이 비용이 더 작으면 갱신!
            if cost < distance[j[0]]:
                distance[j[0]] = cost
                

 

효율적인 방법으로 구현하기

개선된 다익스트라 알고리즘이 존재한다. 이 경우는 시간복잡도가 O(ElogV)가 된다. 위의 간단한 방법에서는, 최단거리가 가장 짧은 노드를 찾기 위해 정말 하나하나 다 탐색했다.  하지만 우리에게는 최소값을 뽑아주는 자료구조가 존재한다. 뭐다? 힙!

import heapq

# 노드의 개수, 간선의 개수를 입력받는다.
n, m = map(int, input().split())
# 시작 노드
start = int(input())
# 노드 정보
graph = [[] for _ in range(n+1)]
# 최단거리
distance = [INF] * (n+1)

# a번 노드에서 b번 노드로 가는 비용은 c다를 입력.
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]))