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

 플로이드-워셜 알고리즘이 전체 노드에 대한 최소거리를 구하는 데 사용된다면, 다익스트라 알고리즘은 특정 노드에 대한 최소거리를 구하는 것에 특화되어 있습니다. 구체적으로는 다음과 같은 과정을 거칩니다.

---

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

5. 위 과정에서 3~4 반복 수행

---

 아래는 기본적인 방법론을 따라 구현한 소스코드입니다.

# n :노드 개수, m : 간선 개수
# start = 시작 노드

INF = int(1e9)

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

for i in range(m):
    # a에서 b로 가는 비용(거리)가 c
    a, b, c = array[i]
    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):
    # initialize
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[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('CANNOT BE REACHED!')
    else:
        print(distance[i], end=' ')

 

 [시작노드, 도착노드, 비용]과 같이 입력을 받아 array에 저장되어 있다고 했을 때, graph는 연결정보를 받는 인접리스트이고, distance는 노드마다 최단경로를 저장할 변수입니다. visited에는 방문 정보를 저장하여 중복된 반복을 방지합니다. 가장 비용이 낮은 노드부터 차례로 인접 노드에 대한 비용 정보를 확인하고, distance 변수를 업데이트합니다.

 

 이렇게 구현할 경우 약 n * (n - 1) 번의 순회를 하게 되며 따라서 시간복잡도는 O(N^2)이 됩니다. 더욱 효율적인 코드를 작성하기 위해서 다음과 같은 방식을 고려할 사항을 고려할 필요가 있습니다.

---

1. 우선순위 큐를 이용하여 노드 정보를 삽입하는 것만으로 최소비용 순으로 정렬시킬 수 있습니다.

2. 한번 방문한 노드는 최소비용임이 보장됩니다.

---

 따라서 우선순위 큐를 지원하는 heapq 라이브러리를 이용하여 코드를 작성하면 다음과 같습니다.

import heapq

INF = int(1e9)

graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1)

for i in range(m):
    # a에서 b로 가는 비용(거리)가 c
    a, b, c = array[i]
    graph[a].append((b, c))
    
def dijkstra(start):
    q = []
    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('INFINITY', end=' ')
    else:
        print(distance[i], end=' ')

 visited 변수가 사라져도 해당 노드에 저장된 distance 변수의 값과 실제 비용을 비교하는 것만으로 방문 여부를 확인할 수 있습니다.

dist, now = heapq.heappop(q)
if distance[now] < dist:
    continue

또한 heapq에 원소를 삽입하는 것만으로 비용순으로 정렬시킬 수 있습니다. 이 때 heapq는 오직 최소 큐만을 지원하므로 무조건 오름차순으로 정렬됩니다. 또한 리스트나 튜플이 들어올 경우 첫번째 원소에 대해서 정렬시키기 때문에, (비용, 노드)와 같은 형태로 삽입해줘야 합니다.

if cost < distance[i[0]]:
    distance[i[0]] = cost
    heapq.heappush(q, (cost, i[0]))

 위의 코드는 E가 간선의 개수, N이 노드의 개수라고 할 때 O(ElogN)이 됩니다.