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

저번에 다뤘던 BFS에서, 노드와 노드간의 거리를 계산할 수 있다고 얘기하였다. 그렇다면 가중치 그래프에선 BFS로 거리를 계산할 수 있을까?
BFS는, 같은 깊이, 즉 인접한 노드들만 탐색하는 방식이기 때문에, BFS만으로는 최단거리를 구하는건 무리가 있다.

그래서 사용하는 알고리즘이 다익스트라 알고리즘이다.
다익스트라 알고리즘은, 가중치가 주어지는 그래프, 즉 각 노드마다의 거리가 다른 그래프에서, 각 노드까지로 가는데에 가장 최소한의 시간, 최단 거리를 구하는 알고리즘으로, 구현이 좀 까다롭고 많이 사용되는 알고리즘의 종류다.

단순히 이차원 리스트 만으로 구현이 가능하지만, 이는 시간 복잡도에서 불리한 구현 방식이고, 많은 사람들이 우선순위큐를 이용하여, 탐색 과정을 줄이곤 한다.
그래서 필자는 최소힙 구조를 이용하여, 우선순위 큐를 만들고, 이를 통하여 최단거리를 구하는 알고리즘을 다루려한다.

1.우선순위 큐란?

큐 자료구조는 FIFO(First Input First Output)구조를 베이스로 한다. 하지만, 우선순위 큐는 우선순위가 가장 높은 순서대로 pop하는 방식을 사용한다. 그렇기 때문에, 코딩을 할 때 우선순위가 높은대로 무언가를 처리하고 싶을 때 사용하곤 한다.
파이썬에선 heapq 라이브러리를 제공하는데, 그래프를 최소 힙 구조로 만들어주고, 큐 자료구조에 있는 pop,push등의 함수를 사용 가능하게 해준다.

다익스트라에선 어떻게 이용하면 좋을까?

최단거리, 즉 노드간 거리가 적은 순으로 정렬(최소 힙)구조를 만들어 준 후에, 거리 계산을 하면, 노드간 거리가 우선순위가 되고, 짧은순으로 처리되기 때문에, 이를 구현 가능하게 해준다.
시간 복잡도 관련해서, 이 최소힙 구조를 사용하게 되면, 최악의 경우 O(logN)시간이 걸리는데, 이를 사용하지 않고 그냥 리스트를 사용하게 된다면 최악의 경우 O(N)이 걸리기 때문에, 시간 복잡도 면에서 우위를 점할 수 있다.

2. 적용

위에서 말한 것 처럼, 노드간의 거리가 우선순위가 되기 때문에, 우리는 노드간의 거리(최단 거리)를 기록할 무언가를 준비해서, 한 노드로부터 모든 노드로까지 가는데에 최단 거리를 구할 수 있을 것이다.
만약 기존 최단 거리로 저장해뒀던 것 보다 더 짧은 거리를 만나게 된다면, 해당 거리를 우선순위 큐에 넣으면, 큐에서 자연스럽게 힙 구조를 완성시키면서, 최단 거리를 갱신해주게된다.
아래의 링크는 위키피디아에서 다익스트라 알고리즘이 어떻게 동작하는지를 보여주는 gif이다.

링크텍스트

기본적으로, 노드간 간선이 존재하지 않는 경우는 값을 무한으로 가정하여, 1번 노드가 3번노드와 연결되어있지 않지만, 2번 노드를 통하여 갈 수 있는 상황일 때, 이 무한대 값을 갱신해주며, 최단 거리 계산이 이루어진다.
코드를 한번 봐보자

import sys
import heapq


input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
INF = 1000000000
distance = [INF] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c)) #-> 튜플


def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start))  # 시작노드 정보 우선순위 큐에 삽입
    distance[start] = 0            # 시작노드->시작노드 거리 기록
    while queue:
        dist, node = heapq.heappop(queue)
        # 큐에서 뽑아낸 거리가 이미 갱신된 거리보다 클 경우(=방문한 셈) 무시
        if distance[node] < dist:
            continue
        # 큐에서 뽑아낸 노드와 연결된 인접노드들 탐색
        for next in graph[node]: #next[0]=노드, next[1]=거리(간선 비용) -> 튜플
           cost = distance[node] + next[1]   # 시작->node거리 + node->node의인접노드 거리
           if cost < distance[next[0]]:      # cost < 시작->node의인접노드 거리
                distance[next[0]] = cost
                heapq.heappush(queue, (cost, next[0]))


dijkstra(start)

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

위 코드로 gif내의 그래프를 넣어 실행 해보면

#예제 입력
6 9
1
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
6 5 9
#예제 출력
0
7
9
20
20
11

각 노드로 도달하는 최단거리가 구해지는 것을 알 수 있다.
이 코드에서, 현재 탐색하는 거리가 이전 저장되어있던 최단 거리보다 짧을 경우에만 우선순위 큐에 넣어서 연산을 하는 것이고, 그 보다 크다면 무시하고 넘어가며 최단 거리를 갱신한다.
노드의 개수가 N개, 간선의 개수가 M개라고 가정하면,
시간 복잡도 면에서 힙 구조를 사용하기 때문에 최악의 경우라도 모든 노드를 탐색하는데 O(logN)의 시간이 걸리고 간선의 개수만큼 거리 갱신을 진행하기 때문에, 최종적으로 O(MlogN)의 시간 복잡도를 갖게된다.

강력하고, 어려운 알고리즘이라고 생각되기 때문에 계속 반복하며, 숙달하여
잘 사용할 수 있도록 해야겠다.