[Algorithm] 다익스트라 알고리즘

다익스트라 알고리즘이란 매 상황마다 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하는 것으로 그리디 알고리즘으로 분류된다. 단계를 거치며 한 번 처리된 노드의 최단거리는 고정되어 더 이상 바뀌지 않는다. 그래서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.

 

다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됩니다. 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야합니다. 

 

 

구현

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)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n+1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)

#모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b,c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
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]
    print(distance)
    # 시작 노드를 제외한 전체 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

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

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

다익스트라 알고리즘 성능을 개선하기 위해선 어떻게 해야하나

우선순위 큐(Priority Queue)를 구현하기 위해서 필요한게 힙(Heap)이다. 

 

import heapq
a = [1,100,7,4,5,25]
#/Heap을 이용한 정렬하기 (오름차순)/#
def sort(a):
    result = []
    heap = [] 
    for value in a:
        heapq.heappush(heap, value)

    for i in range(len(heap)):
        result.append(heapq.heappop(heap))
    return result
#/Heap을 이용한 정렬하기 (내림차순)/#
def sort_reverse(a):
    result = []
    heap = []
    for value in a:
        heapq.heappush(heap, -value)
    
    for i in range(len(heap)):
        result.append(heapq.heappop(heap))
    return result

print(sort(a))
print(sort_reverse(a))

개선된 다익스트라 알고리즘 (최소힙 활용)

힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)입니다. 

노드를 하나씩 꺼내 검사하는 반복문(while문)은 노드의 개수 V이상의 횟수로는 처리되지 않습니다. 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수행될 수 있습니다. 

직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 뺴내는 연산과 매우 유사합니다. 

시간 복잡도를 O(ElogE)로 판단할 수 있습니다. 중복 간선을 포함하지 않는 경우에 이를 O(ElogV)로 정리할 수 있습니다. 

# 다익스트라 알고리즘 구현하기

import sys
import heapq

# 노드와 간선의 갯수를 받는다
n ,m = map(int, input().split())
# 시작 노드를 받는다. 
start = int(input())
# 노드와 간선에 대한 정보를 바탕으로 graph를 만든다.
graph = [[] for i in range(n+1)]

for i in range(n+1):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
# 최단 거리 테이블을 초기화 한다. 
distance = [[] for i in range(n+1)]
# 다익스트라를 구현한다. 

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # 거리와 첫 노드를 넣어준다. 
    while q:
        dist, now = heapq.heappop(q) # 거리가 최소인 노드를 알려준다. 
        if distance[now] < dist: # 방문한 노드인지를 판별하기 위해서 distance table이 갱신되었는지를 판별한다. 
            continue
        for i in graph[now]: # 현재 노드와 인접한 노드들을 확인
            cost = dist + i[0]
            if cost <= distance[i[1]]: # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 짧은 경우
                distance[i[1]] = cost
                heapq.heappush(q, (cost, i[0]))

 

아래 동영상에 대한 내용을 그대로 담았다.

https://www.youtube.com/watch?v=acqm9mM1P6o&t=978s