다익스트라 알고리즘
다익스트라 알고리즘은 최단거리를 구하는 알고리즘입니다. 다익스트라 알고리즘을 사용하면, 하나의 노드에서 다른 모든 노드까지의 거리를 구할 수 있습니다. 개인적으로 개념을 이해하는 것은 어렵지 않았지만, 구현하는 것에서 복잡하다고 느껴졌습니다. 구현을 위주로 글을 써보겠습니다.
다익스트라 알고리즘의 원리
다익스트라 알고리즘은 아래의 두 문장으로 정리될 수 있습니다.
-
최단거리를 구할 노드에서 시작하여, 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택합니다.
-
노드를 돌아가면서, 더 거리가 짧은 나오면 값을 갱신하여 넣습니다.
다익스트라 알고리즘 사용 예시
- 가중치 방향 그래프를 통해 다익스트라 알고리즘의 원리를 더 자세히 살펴 보겠습니다.
- 노드 1에서부터 다른 모든 노드까지의 최단 경로를 구해보겠습니다.
- 초기에는 모두 거리를 무한으로 설정합니다.
| 거리 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| x | INF | INF | INF | INF | INF |
- 처음에는 자기 자신까지의 거리를 0으로 놓고 노드 1과 직접 연결된 노드까지의 거리를 입력합니다.
- 이제 1번 노드는 방문처리합니다.
| 거리 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| x | 0 | 1 | 3 | INF | INF |
- 방문처리되지 않은 노드 중 입력된 거리가 가장 짧은 2번 노드를 선택합니다.
- 2를 기준으로 하였을 때 거리를 구하면, 3번 노드까지의 거리가 1 + 1로 2가 됩니다. 기존에 입력된 3보다 작으므로 값을 갱신합니다.
- 4번 까지의 거리는 1 + 5로 6이 됩니다.
- 이제 2번 노드는 방문처리합니다.
| 거리 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| x | 0 | 1 | 2 | 6 | INF |
- 방문처리되지 않은 노드 중 입력된 거리가 가장 짧은 3번 노드를 선택합니다.
- 3번 노드를 기준으로 하였을 때, 4번 노드까지의 거리는 2 + 2로 4가 됩니다. 기존에 입력된 6보다 작은 값이므로 값을 갱신합니다.
| 거리 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| x | 0 | 1 | 2 | 4 | INF |
- 방문처리되지 않은 노드 중 입력된 거리가 가장 짧은 3번 노드를 선택합니다.
- 연결된 노드가 없으므로 최단거리 구하기를 마칩니다.
- 1번 노드로 부터 다른 모든 노드로부터의 최단거리는 아래의 표와 같습니다.
| 거리 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| x | 0 | 1 | 2 | 4 | INF |
구현
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]이 구현 방법을 사용했을 때, 현재 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 선택할 때 반복문을 사용합니다. 이 부분을 heap으로 구현하면, 코드의 길이도 짧아지도 시간복잡도도 낮추는 효과를 가져올 수 있습니다.
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]
개발