[최단 경로] 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘

다익스트라 알고리즘은 최단경로를 구하는 알고리즘 중 하나이다.

다익스트라 알고리즘을 사용하면 하나의 노드에서 다른 모든 노드까지의 거리를 구할 수 있다.

 

다익스트라 알고리즘 원리

다익스트라 알고리즘은 아래의 두 문장으로 정리될 수 있다.

1. 최단거리를 구할 노드에서 시작하여, 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택한다.
2. 노드를 돌아가면서, 더 거리가 짧다면 값을 갱신한다.

 

(a) 노드 0에서 거리를 기록한 후, 가장 가까운 노드인 1번노드를 선택한다

(b) 선택된 1번노드를 기준으로, 거리가 최소가 되도록 갱신한다. 0번노드에서 3번 노드로 바로 갈 경우, 거리가 무한대이지만, 1번노드를 거쳐가면 거리가 6이므로 3번노드까지의 거리를 6으로 갱신한다. 가장 가까운 노드는 4번노드이므로 4번노드를 선택한다.  

(c) 3번노드와 2번노드의 경우, 선택된 4번노드를 거쳐서 가는 것이 더 가까우므로, 0->3번노드까지의 거리와 0->2번노드까지의 거리를 갱신한다. 이후, 가장 가까운 노드는 2번노드이므로 2번노드를 선택한다.  

(d) 갱신할 것이 없으므로,갱신하지 않는다. 가장 가까운 노드는 3번노드이므로 3번노드를 선택한다.  

(e) 갱신할 것이 없으므로,갱신하지 않는다. 3번노드를 방문처리한 후, 완료한다

 

 

다익스트라 알고리즘 사용 예시

<예시1> 노드 1에서 다른 모든 노느까지의 최단경로 구하기

 

 

 

STEP0) 초기에는 모두 거리를 무한으로 설정한다.

거리	1	2	3	4	5
	INF	INF	INF	INF	INF

 

 

 

 

STEP1) 자기 자신(노드 1)의 거리는 0으로 두고, 노드 1과 직접 연결된 노드까지의 거리를 입력한다

1번 노드 기준

 

거리	1	2	3	4	5
	0	1	3	INF	INF

 

 

 

 

STEP2) 방문처리가 되지 않은 노드 중, 입력된 거리가 가장 짧은 노드를 선택한 후, 그 노드를 기준으로 거리를 비교하여 최단거리로 갱신한다. 이후 선택한 노드를 방문처리를 한다.

 

• 2번 노드가 선택된다.
• 2번 노드를 기준으로 했을 때 거리를 구해보면 3번 노드까지 거리가 1+1로 2가 된다. 기존에 입력된 3보다 작으므로 값을 갱신한다.
• 4번까지의 거리는 1+5 = 6이 된다. 기존에 입력된 INF보다 작으므로 6으로 갱신한다.
• 이제 2번 노드는 방문처리 한다.

거리	1	2	3	4	5
	0	1	2	6	INF

 

 

 

STEP3) 위 STEP 2을 반복한다

 

• 3번 노드가 선택된다. (방문처리 되지 않은 노드 중 입력된 거리가 가장 짧은 노드)
• 3번 노드를 기준으로 했을 때 거리를 구해보면 4번 노드까지 거리가 2+2로 4가 된다. 기존에 입력된 6보다 작으므로 값을 갱신한다.
• 이제 3번 노드는 방문처리 한다.

거리	1	2	3	4	5
	0	1	2	4	INF

 

 

 

 

 

• 4번 노드가 선택된다. (방문처리 되지 않은 노드 중 입력된 거리가 가장 짧은 노드)
• 연결된 노드가 없으므로 최단거리 구하기를 마친다.
• 1번 노드로부터 다른 모든 노드까지 최단거리는 아래 표와 같다.

거리	1	2	3	4	5
	0	1	2	4	INF

 

 

수도코드

 

 

코드

Python

 1) 반복문 사용 

이 구현 방법을 사용했을 때, 현재 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 선택할 때 반복문을 사용한다.

 

이 부분을 heap으로 구현하면, 코드의 길이도 짧아지도 시간복잡도도 낮추는 효과를 가져올 수 있다.

n, m = map(int, input().split())
k = int(input())                 # 시작할 노드
INF = 1e8

graph = [[] for _ in range(n+1)] # 1번 노드부터 시작하므로 하나더 추가

visited = [False] * (n+1)
distance = [INF] * (n+1)

for _ in range(m):
  u, v, w = map(int, input().split()) # u: 출발노드, v: 도착노드, w: 연결된 간선의 가중치
  graph[u].append((v, w))             # 거리 정보와 도착노드를 같이 입력합니다.

def get_smallest_node():
  min_val = INF
  index = 0
  for i in range(1, n+1):
    if distance[i] < min_val and not visited[i]:
      min_val = distance[i]
      index = i
  return index

def dijkstra(start):
  distance[start] = 0 # 시작 노드는 0으로 초기화
  visited[start] = True

  for i in graph[start]:
    distance[i[0]] = i[1] # 시작 노드와 연결된 노도들의 거리 입력

  for _ in range(n-1):
    now = get_smallest_node() # 거리가 구해진 노드 중 가장 짧은 거리인 것을 선택
    visited[now] = True       # 방문 처리

    for j in graph[now]:
      if distance[now] + j[1] < distance[j[0]]: # 기존에 입력된 값보다 더 작은 거리가 나온다면,
        distance[j[0]]= distance[now] + j[1]    # 값을 갱신한다.

dijkstra(k)
print(distance)

# 5 6
# 1
# 5 1 1
# 1 2 1
# 1 3 3
# 2 3 1
# 2 4 5
# 3 4 2
# 예시를 입력하면 아래와 같이 나온다. 0번 인덱스는 편의상 만든 것이기에 무시하면 되고, 예상했던대로 0 1 2 4 INF 가 나오는것을 확인할 수 있다.
# [100000000.0, 0, 1, 2, 4, 100000000.0]

 

 2) heap을 활용한 구현

n, m = map(int, input().split())
k = int(input())                 # 시작할 노드
INF = 1e8

graph = [[] for _ in range(n+1)] # 1번 노드부터 시작하므로 하나더 추가

distance = [INF] * (n+1)

for _ in range(m):
  u, v, w = map(int, input().split()) # u: 출발노드, v: 도착노드, w: 연결된 간선의 가중치
  graph[u].append((v, w))             # 거리 정보와 도착노드를 같이 입력합니다.


import heapq

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]:     # 연결된 모든 노드 탐색
      if dist+i[1] < distance[i[0]]: # 기존에 입력되어있는 값보다 크다면
        distance[i[0]] = dist+i[1]   #
        heapq.heappush(q, (dist+i[1], i[0]))
dijkstra(k)
print(distance)

# 5 6
# 1
# 5 1 1
# 1 2 1
# 1 3 3
# 2 3 1
# 2 4 5
# 3 4 2
# 예시를 입력하면 아래와 같이 나온다. 0번 인덱스는 편의상 만든 것이기에 무시하면 되고, 예상했던대오 0 1 2 4 INF 가 나오는것을 확인할 수 있다.
# [100000000.0, 0, 1, 2, 4, 100000000.0]