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

다익스트라 알고리즘의 구현에 대해서 다뤄보겠다. 앞서 다익스트라 알고리즘 (1)에서 설명했듯이 다익스트라 알고리즘 구현은 2가지 방법으로 가능하다.

 

• 간단한 구현, 높은 시간 복잡도를 가지고 있는 방법
• 우선순위 큐를 사용한 빠른 시간복잡도를 가지고 있는 방법

우선 간단한 구현, 높은 시간복잡도를 가지고 있는 방법의 코드이다.

 

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())
  graph[a].append((b,c))
 
def GetSmallestNode():
  minValue = INF
  index = 0
  for i in range(1, n+1):
    if distance[i] < minValue and not visited[i]:
      minValue = 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]
  for i in range(n-1):
    now = GetSmallestNode()
    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])

 

GetSmallestNode 함수는 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 찾아주는 기능을 한다.

 

다음은 우선순위 큐를 사용한 빠른 시간복잡도를 가지고 있는 방법의 코드이다.

 

import heapq
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)]
distance = [INF] * (n +1)
 
for _ in range(m):
  a, b, c = map(int, input().split())
  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")
  else:
    print(distance[i])

 

두 알고리즘의 차이점은 최단 거리가 짧은 노드를 가져오는 법에 있다. 첫 번째 방법은 거리를 담아둔 배열에서 모든 원서를 하나씩 전부 확인하여 값을 가져오고, 두 번째 방법은 우선순위 큐를 활용하여 heappop을 사용하여 배열의 값을 가져온다.

 

탐색을 하여 값을 가져오는 것과 배열의 값을 가져오는 것에서 속도 차이가 발생하여 결국에 시간 복잡도까지 달라지게 된 것이다.