« 2024/07 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

다익스트라(Dijkstra)

다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다.

특정한 하나의 정점 → 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이 때 음의 간선은 포함할 수 없다. (현실세계에 사용하기 매우 적합한 알고리즘 중 하나이다.)

👉 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는?

최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. 작은 문제가 큰 문제의 부분집합에 속해있다.

👉 그리디 알고리즘의 일종인 이유는?

매번 ‘가장 비용이 적은 노드’를 선택하기 때문이다.

기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다.

다음의 그래프에서 노드 1에서 2,3,4 노드까지의 최단 거리를 구하려고 한다.

각 노드까지의 최단 거리는 간선의 길이인 3/6/7 이 된다.

하지만 왼쪽과 달리 오른쪽 그림에서, 1부터 3까지의 최단 거리를 구할 때 2를 거친다면, 3+1=4로 훨씬 짧은 최단거리를 얻을 수 있다.

다시 말해, 다익스트라 알고리즘은 ‘현재까지 알고 있던 최단 거리를 계속해서 갱신’해간다.

구체적인 동작 과정

출발 노드를 설정한다.

출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.

방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.

위 과정에서 3번~4번을 반복한다.

1. 출발 노드를 설정하고 그것을 기준으로 최소 비용을 저장한다.

이런 그래프는 보통 이차원 배열 형태로 처리해야 한다.

초기 상태에서는 다른 모든 노드로 가는 최단 거리를 무한으로 설정한다.
- 가장 간단 방법은 지수 표기법 사용 1e9, 간선이 정수형이라면 int(1e9)로 초기화 한다.

이런 형태로 i 번째 노드에서 j번째 노드까지의 비용을 초기 최소 비용으로 저장한다.

	j=1	j=2	j=3	j=4	j=5	j=6
i=1	0	2	5	1	무한	무한
j=2	0	0	3	2	무한	무한
i=3	무한	3	0	무한	무한	5
i=4	무한	무한	3	0	1	무한
i=5	무한	무한	1	무한	0	2
i=6	무한	무한	무한	무한	무한	0

2. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

출발 노드를 1번으로 설정하고, 1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다. 즉, 1번 노드와 연결된 모든 간선을 하나씩 확인하면 된다.

	j=1	j=2	j=3	j=4	j=5	j=6
i=1	0	2	5	1	무한	무한

방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다. → 4번노드 선택

4번노드와 연결된 노드는 3번과 5번

3. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.

3번과 5번 노드로 가는 최소 비용을 업데이트 한다.

	j=1	j=2	j=3	j=4	j=5	j=6
i=1	0	2	4	1	2	무한

4. 위 과정을 반복한다.

최단 거리가 짧은 노드를 선택한다. → 2번노드 선택

2번노드와 연결된 노드는 4번과 3번

2를 거쳐 3으로 가는 비용: 5

2를 거쳐 4로 가는 비용: 4

최단 거리를 더 짧게 갱신할 수 있는 방법은 없으므로 그대로 유지.

	j=1	j=2	j=3	j=4	j=5	j=6
i=1	0	2	4	1	2	무한

다시 최단 거리가 짧은 노드 선택 → 5번노드

5번노드와 연결된 노드는 3번과 6번

5를 거쳐 3으로 가는 비용: 3

5를 거쳐 6으로 가는 비용: 4

둘 다 최단거리 업데이트 가능.

	j=1	j=2	j=3	j=4	j=5	j=6
i=1	0	2	3	1	2	4

다시 최단 거리가 짧은 노드 선택 → 3번 노드

3번 노드와 연결된 노드는 2번과 6번

3을 거쳐 2번으로 가는 비용: 6

3을 거쳐 6번으로 가는 비용: 8

둘 다 최단거리 업데이트 불가능

	j=1	j=2	j=3	j=4	j=5	j=6
i=1	0	2	3	1	2	4

다시 최단 거리가 짧은 노드 선택 → 6번 노드

6번 노드와 연결된 노드는 없음.

	j=1	j=2	j=3	j=4	j=5	j=6
i=1	0	2	3	1	2	4

👍 이렇게 최단 거리 테이블이 완성되었다.

최단 거리 테이블은, 1번 노드로부터 출발했을 때 2번/3번/4번/5번/6번 노드까지 가기 위한 최단 경로가 각각 2/3/1/2/4 라는 의미이다.

짚고 넘어가야 할 것

다익스트라 알고리즘에서는 ‘최단거리’가 완전히 선택된 노드이므로 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.

예를 들어 4번 노드가 선택되어서 4번 노드를 거쳐 이동할 수 있는 경로를 확인했다. 그 이후의 스텝이 진행될 때 4번 노드에 대한 최단 거리는 더 이상 감소하지 않았다.

즉, 다익스트라 알고리즘은 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.

또한 코딩 테스트에서는 대체로 특정노드 → 특정 노드까지의 최단 거리 출력이 요청되는데 완벽한 최단 경로를 구하려면 최단 거리 테이블만 구하지 않고 코드 수정이 조금 필요하다.

코드 구현

첫번째 방법, 쉬운 구현이지만 느린 코드

# 다익스트라 쉬운 구현, 조금 느린 버전
import sys
input = sys.stdin.readline
INF = int(1e9)

# 노드, 간선 개수 입력
n, m = map(int, input().split())
# 시작 노드 입력
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())
    # a번 노드에서 b번 노드로 가는 비용이 c
    graph[a].append((b, c))
    
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
# 모든 노드를 한번씩 확인해봐야 함 --> O(V)
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):    # O(V^2)
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    visited[start] = True
    # 방문한 노드의 순간에서 distance 를 갱신한다. 
    # start에 연결되어 있는 노드들에 대한 거리테이블을 갱신한다.
    # j[0]:b, j[1]:c
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복 --> start를 하고 다음단계 시작하는 것
    for i in range(n-1):    # O(V-1)
        now = get_smallest_node()   # O(V)
        visited[now] = True
        
        # 현재 노드와 연결된 다른 노드 확인
        for j in graph[now]:
            cost = distance[now] + j[1] # now 노드를 거쳐서 현재까지 소요된 비용 계산
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
                distance[j[0]] = cost

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    # 도달할 수 없는 경우, 무한이라고 출력
    if distance[i] == INF:
        print('무한')
    # 도달할 수 있는 경우, 거리를 출력
    else:
        print(distance[i])

시간 복잡도는 $O(V^2)$

최단 거리가 가장 짧은 노드를 선형 탐색 + 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문에

노드의 수가 5,000개 이하라면 이 방법으로도 풀 수 있지만 10,000개가 넘어간다면 이 코드로 해결하기는 힘들다.

두번째 방법, 까다로운 구현이지만 빠른 방법

각 단계에서 ‘최단 거리가 가장 짦은 노드’를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체한다.

효과: get_smallest_node() 를 작성할 필요가 없어서 훨씬 빨리 찾을 수 있다.

우선순위 큐는 파이썬의 heapq를 활용한다.

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())
    # a -> b 의 비용이 c
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입 (거리, 노드)의 형태로
    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('무한')
    else:
        print(distance[i])

시간복잡도는 $O(ElogV)$ 으로 훨씬 빠르다.

다익스트라 시간복잡도 분석

노드의 개수 V, 간선의 개수 E 일 때, 다익스트라 알고리즘의 시간복잡도는 $O(ElogV)$ 임을 분석해보자.

queue에서 노드를 하나씩 꺼내 검사하는 while 문 → 노드의 개수 V 이상의 횟수로는 반복되지 않는다. 왜냐하면 한번 처리된 노드(=방문한 노드)는 검사하지 않기 때문이다.

또한 V번 반복될 때 까지 각각 자신과 연결된 간선들을 모두 확인한다. → pop한 노드에 연결된 다른 노드를 확인하는 횟수는 ‘총 최대 간선의 개수 E’ 만큼이다.

이 과정은,

E 개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다. 따라서 최대 E개의 간선 정보를 힙에 넣었다가 빼는 경우로 볼 수 있으므로 → $O(ElogE)$ 임을 이해. (힙의 삽입, 삭제는 $O(logN)$ 이다.)

중복이 없다면, $E < V^2$ 이므로, $logE < log V^2$ 이다.

이것은, $O(logE) < O(2logV) = O(logV)$ 가 될 수 있고,

$O(ElogE) = O(ElogV)$ 로 볼 수 있다.

정리

다익스트라는 최단 경로 알고리즘 중 하나다.

리스트를 사용해 구현할 수 있지만 우선순위 큐를 사용하면 시간 복잡도를 줄일 수 있다.

우선순위 큐는 힙 자료구조를 사용해 구현할 수 있다.

파이썬에는 PriorityQueue와 heapq 라이브러리 모두 존재하는데, 일반적으로 heapq가 더 빠르게 동작한다.

파이썬 라이브러리는 기본적으로 최소 힙 구조를 이용한다.

참조

https://m.blog.naver.com/ndb796/221234424646

Uploaded by N2T

[Programmers] 모의고사 (0)	2023.03.30
[BOJ] 4485번 - __녹색 옷 입은 애가 젤다지?__ (0)	2023.03.29
[알고리즘] 누적합, 구현 (0)	2023.03.28
[알고리즘] 시간복잡도, 빅오표기법, 공간복잡도 (0)	2023.03.28
[BOJ] 1446번 - 지름길 (0)	2023.03.27

생각하는 아져씨