[알고리즘] 최단경로 - 다익스트라 알고리즘 (Dijkstra's algorithm)

동빈나님의 이코테 강의를 보고 제 생각을 더해 정리해 보았습니다.

풀이 언어는 파이썬을 사용했습니다.

 

목차

• 최단 경로 문제
• 다익스트라 알고리즘
• 우선순위 큐를 사용한 다익스트라 알고리즘

최단 경로 문제

최단 경로 문제 중 한 시작점으로 부터 다른 노드 까지 가는데 비용이 얼마나 걸리는 지를 구할 때 사용하는 알고리즘이 다익스트라 알고리즘 입니다.

 

기본적으로 최단 경로 문제는 방향이 있고 가중치가 있는 그래프가 주어집니다.

 

따라서 위의 그래프는 다음과 같이 입력을 받습니다.

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

코드에선 다음과 같은 2차원 배열로 구현 됩니다.

[[], [(2, 2), (3, 5), (4, 1)], [(3, 3), (4, 2)], [(2, 3), (6, 5)], [(3, 3), (5, 1)], [(3, 1), (6, 2)], []]

다익스트라 알고리즘

다익스트라 알고리즘은 그리디 알고리즘의 방식으로 각 노드에 대해 최선의 경우를 찾습니다.

과정은 다음과 같습니다.

 

1. 방문하지 않은 노드 중 가장 거리가 짧은 노드를 선택하고 방문했다는 표시를 남깁니다.

2. 선택한 노드와 연결된 다른 노드(선택한 노드에서 갈 수 있는 노드)를 모두 방문합니다.

3. 방문한 노드를 검사합니다. 

    3-1. 방문한 노드의 기존 거리와 방문한 노드를 선택한 노드를 통해 가는 거리비교

    3-2.  것이 더 비용이 낮다면 방문한 노드를 갱신

4. 1~3의 과정을 N번 반복합니다. (모든 노드를 한번씩 선택)

 

파이썬 코드는 다음과 같습니다.

import sys
readline = sys.stdin.readline
INF = 100

N, M = map(int, readline().split())
start = int(readline())

graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
distance = [INF] * (N+1)

for _ in range(M):
    a, b, c = map(int, readline().split())
    # a 노드에서 b 노드로 가능 비용이 c
    graph[a].append((b, c))

def get_smallest_node():
    min_distance = INF
    index = 0
    # 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택
    for i in range(1, N + 1):
        if distance[i] < min_distance and not visited[i]:
            min_distance = distance[i]
            index = i

    return index

def dijkstra(start):
    # 시작 노드 초기화
    distance[start] = 0

    # N개의 노드에 대해 반복
    for _ in range(N):
        cur = get_smallest_node()
        visited[cur] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for v, w in graph[cur]:
            cost = distance[cur] + w
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧으면 갱신
            if cost < distance[v]:
                distance[v] = cost

dijkstra(start)

# 각 노드에 대해 시작점 부터의 거리를 출력
for i in distance[1:]:
    print(i if i != INF else 'INF')

 

N개 중 가장 거리가 짧은 노드를 선택하고 O(N), 이를 N 번 반복하기 O(N) 때문에 O(N^2)의 시간 복잡도를 갖습니다.

보통 정점 수를 V로 하여 O(V^2)로 표현합니다.

 

일반적으로 코딩테스트 문제에선 시간초과가 발생합니다. 이 때문에 코딩테스트에선 우선순위 큐를 사용하여 개선한 다익스트라 알고리즘 코드를 사용해야 합니다.

 

우선순위 큐를 사용한 다익스트라 알고리즘

똑같은 작동방식에서 우선순위 큐를 위한 자료구조인 heap을 사용하여 다익스트라 알고리즘을 구현할 수 있습니다.

N개 중 가장 거리가 짧은 노드를 선택하는 과정을 heap을 사용하여 개선할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

import heapq
import sys
readline = sys.stdin.readline
INF = 100000000

N, M = map(int, readline().split())
start = int(readline())

graph = [[] for _ in range(N + 1)]
distance = [INF] * (N+1)

for _ in range(M):
    a, b, c = map(int, readline().split())
    # a 노드 -> b 노드 : 비용 c
    graph[a].append((b, c))

def dijkstra(start):
    q = []

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        cur_dist, cur_v = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있다면 무시
        if distance[cur_v] < cur_dist:
            continue
        # 현재 노드오 연결된 다른 노드들 확인
        for v, w in graph[cur_v]:
            cost = cur_dist + w
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧으면 갱신
            if cost < distance[v]:
                distance[v] = cost
                # 갱신한 노드를 힙에 푸시
                heapq.heappush(q, (cost, v))

dijkstra(start)

for i in distance[1:]:
    print(i if i != INF else 'INF')

 

이 코드의 시간 복잡도는 간선의 갯수로 표현하여 O(ElogE) 인데,

E는 최대 V^2일 수 있으므로 O(Elog(V^2)) -> O(ElogV) 로 표현 합니다.