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

오늘의 포스팅은 프림 알고리즘(Prim's)의 변형인 다익스트라 (Dijkstra) 알고리즘입니다!

다익스트라 알고리즘은 데이크스트라라고도 불리는데욥

TMI)백준 알고리즘분류에는 데이크스트라라고 분류되어 있네욤,,,

여담으로 다익스트라 알고리즘은 1956년에 네덜란드 태생 컴퓨터 과학자인 다익스트라에 의해 개발되었다고 하는데욥

까페에서 피앙세를 기다리던 도중 20분정도만에 아이디어를 생각해낸 알고리즘이라고 합니다,,,,

 

다익스트라 알고리즘은 특정 노드에서 모든 노드로 가는 최단 경로(Shortest path)를 구하는 알고리즘인데요

양의 가중치를 가지는 그래프에서만 사용 가능합니다! (음의 가중치는 벨만-포드 알고리즘 사용)

 

다익스트라 알고리즘은 greedy알고리즘에 속하기도 하는데욥

매번 현재 노드에서 가장 가까운, 가중치가 가장 작은 간선(edge)를 선택하기 때문입니다!

이로인해 현재 상황에서 당장 좋은 것만 고르는 방법인 greedy 알고리즘으로도 바라볼 수 있습니다

https://hipposdata.tistory.com/96

그리디 알고리즘(Greedy Algorithm)

 

특히 활용방안은 매우 다양한데요 지도, 네트워크 시스템, 경로최적화 등 그래프구조로 표현가능한 문제에서 다양하게 활용할 수 있습니다!

 

# 동작과정 

다익스트라 알고리즘의 동작과정은 총 3가지로 요약할 수 있습니다!

1. 그래프 구현 및 최단거리 리스트, 방문 리스트 생성

그래프 구현: 인접리스트를 이용(메모리 효율성)

최단 거리 리스트:  초기에는 출발 노드의 거리는 0, 나머지 노드들의 거리는 무한대로 설정

방문 리스트: 초기에는 모두 방문되지 않은 상태로 설정

 

2. 최단 거리 값이 가장 작은 노드 선택 및 최단거리 리스트 업데이트 

현재 방문하지 않은 정점 중에서 최단 거리 값이 가장 작은 노드를 선택하여,

이웃 노드의 최단거리를 업데이트합니다

 

업데이트 방식은 

(이웃노드의 최단거리값)과 (현재 노드의 최단거리값 + 현재 노드에서 이웃 노드까지의 가중치)

(이웃노드의 최단거리값)  > (현재 노드의 최단거리값 + 현재 노드에서 이웃 노드까지의 가중치)

 

두 값을 비교하여 후자의 값이 더 작을시 해당 값으로 교체해줍니다

이후 현재 노드를 방문표시합니다

 

3. 모든 노드 방문할 때까지 2번과정 반복

모든 노드가 방문되면, 최단 거리 리스트에는 출발 노드에서 각 노드까지의 최단 거리 값이 저장됩니다!

 

 

구체적인 예시를 통해 자세히 살펴보겠습니다

12345 다섯개의 노드로 이루어진 방향 그래프에서 다익스트라 알고리즘을 적용한 예시를 살펴보겠습니다!

 

최종적으로 각 노드별로 최단거리가 반환됩니다!

# Python 코드

인접리스트, 최단거리 리스트, 방문기록 리스트, 우선순위큐가 필요합니다!

 

최단거리 리스트의 초기 무한대 값은  sys.maxsize 연산을 이용하여 적용하였습니다

 

우선순위 큐 자료구조를 이용하여 거리와 인접노드를 삽입하며 매번 거리가 가까운 노드를 뽑도록 합니다

우선순위 큐는 heapq 라이브러리를 이용하여 구현하였습니다

import sys

import heapq

v,e = map(int,sys.stdin.readline().split())

k = int(sys.stdin.readline())

# 인접리스트 생성

grp = [[] for i in range(v+1)]

for _ in range(e):

    u,v2,w =  map(int,sys.stdin.readline().split())

    grp[u].append((v2,w))

# 거리기록

dst = [sys.maxsize] * (v+1) # 거리기록 / 초기 임의 최대값상수

dst[k] = 0 # 시작지점 거리 0

vst = [False] * (v+1)

q = [] # 우선순위 큐 리스트 생성

heapq.heappush(q,(0,k))# 초기거리 ,시작지점을 큐에 삽입 / 최단거리 기준으로 최소값 뽑아야 하기 때문

while len(q) >0:

    distance ,node = heapq.heappop(q)

    if vst[node] : # 방문한적 있다면 넘어감

        continue

    vst[node] = True # 노드 방문처리

    for i in grp[node]: # 인접노드들 계산

        next_node = i[0]

        weight = i[1]

        if dst[next_node] > distance + weight: #최소거리 업데이트

            dst[next_node] = distance + weight

            heapq.heappush(q,(dst[next_node],next_node)) # 큐에 노드 삽입

 

# 성능분석 - 시간복잡도

V-> 노드의 수

E-> 간선의 수

 

우선순위 큐를 사용시 O(Elog⁡V) 의 시간복잡도를 보이는데요

우선순위 큐에서 현재까지 가장 짧은 거리를 가지는 노드 선택에 O(log V) 시간복잡도를 가지며 

이를 모든 간선에 대해 적용하므로

O(E) X O(log V) = O(Elog⁡V)

 

# 관련문제

백준 1753번 - 최단경로

https://www.acmicpc.net/problem/1753

 

백준  1916번 - 최소비용 구하기 

https://www.acmicpc.net/problem/1916

 

백준  1854번 - K번째 최단경로 찾기

https://www.acmicpc.net/problem/1854

 

# reference

파이썬 자료구조와 알고리즘: for beginner. (2021). 대한민국: 한빛아카데미.

Do it! 알고리즘 코딩 테스트 - 파이썬 편(김종관 저/이지스퍼블리싱 (주))