![[Algorithm/Python] 다익스트라 최단 경로 알고리즘이란? || dijkstra](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fc8RpKX%2FbtsdlLCJlID%2FU8TMOktzxGG089miUdWemk%2Fimg.png)
들어가며
본 포스팅에서는 다익스트라 최단 경로 알고리즘에 대해 소개합니다.
📌 다익스트라 최단 경로 알고리즘이란?
다익스트라 최단 경로 알고리즘이란, 가장 짧은 경로를 찾기 위한 알고리즘으로, 음의 간선(0보다 작은 값을 가진 간선)이 없을 때에 적용할 수 있는 알고리즘입니다.
1️⃣ 출발 노드를 설정합니다.
2️⃣ 최단 거리 테이블 초기화(무한으로 설정)합니다.
3️⃣ 방문하지 않은 노드 중에 최단 거리 테이블에서 최단 거리가 가장 짧은 노드를 선택합니다.
4️⃣ 선택한 노드를 거쳐 다른 노드로 가는 거리를 계산합니다.
5️⃣ 계산된 거리가 최단 거리 테이블의 거리보다 짧을 경우, 갱신합니다.
6️⃣ 위의 3️⃣4️⃣5️⃣를 반복합니다.
가장 최단 거리의 노드를 선택하여 주변 간선을 확인합니다. 더 짧은 거리가 있다면, 갱신하며 이 과정을 반복한다는 점에서 그리디 알고리즘으로 볼 수 있습니다.
1. 출발 노드를 1번으로 설정합니다. 최단 거리 테이블을 무한으로 초기화합니다. 출발 노드인 1번의 최단 거리는 0입니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
2. 방문하지 않은 노드 중에 최단 거리 테이블에서 최단 거리가 가장 짧은 노드인 1번을 선택합니다. 1번을 거쳐 다른 노드로 가는 거리를 계산합니다. 각각 2번(0 + 2), 3번(0 + 5), 4번(0 + 1)노드입니다.
계산된 거리와 최단 거리 테이블에서의 거리를 비교해보면, 모두 무한으로 설정되어있으므로, 세 노드에 대한 값이 모두 갱신됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
이미 처리된 간선은 점선으로, 노드는 회색으로 표기하였습니다.
3. 그 다음으로 선택되는 노드는 4번입니다. 4번을 거쳐 다른 노드로 가는 거리를 계산합니다. 각각 3번(1 + 3), 5번(1 + 1)입니다. 모두 기존 최단 거리 테이블에서의 거리보다 짧으므로 갱신됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
4. 그 다음으로 선택되는 노드는 2번입니다. 2번을 거쳐 다른 노드로 가는 거리를 계산합니다. 각각 3번(2 + 3), 4번(2 + 2)입니다. 모두 기존 최단 거리 테이블에서의 거리보다 크므로, 갱신이 되지 않습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
5. 그 다음으로 선택되는 노드는 5번입니다. 5번을 거쳐 다른 노드로 가는 거리를 계산합니다. 각각 3번(2 + 1), 6번(2 + 2)입니다. 모두 기존 최단 거리 테이블에서의 거리보다 짧으므로 갱신합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
6. 그 다음으로 선택되는 노드는 3번입니다. 3번을 거쳐 다른 노드로 가는 거리를 계산합니다. 각각 2번(3 + 2), 6번(3 + 5)입니다. 모두 기존 최단 거리 테이블에서의 거리보다 크므로, 갱신이 되지 않습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
7. 마지막으로 6번 노드가 선택됩니다. 최종 최단 거리 테이블은 다음과 같습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
📌 간단한 다익스트라 알고리즘
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ 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))
- INF : 무한을 의미하며, 10억입니다.
- 1부터 N + 1번 노드를 그래프로 입력받고, visited로 방문 여부를, distance로 최단 거리를 체크합니다.
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- 1번부터 N + 1번 노드까지 탐색하며, 방문하지 않았으며, 최단 거리 테이블(distance)에서 거리가 가장 짧은 노드를 탐색합니다.
def dijkstra(start):
distance[start] = 0
visited[start] = True
for b, c in graph[start]:
distance[b] = c
for _ in range(n - 1):
now = get_smallest_node()
visited[now] = True
for b, c in graph[now]:
distance[b] = min(distance[b], distance[now] + c)
# cost = distance[now] + c
# if cost < distance[b]:
# distance[b] = cost- 먼저 출발 노드에 대한 최단 거리를 0으로 설정하며 방문 처리를 합니다.
- 출발 노드와 연결된 노드에 대한 거리를 distance에 담아줍니다.
- 그 후, 출발 노드를 제외한 n - 1개의 노드에 대해 반복합니다.
- 최단 거리 테이블(distance)에서 가장 거리가 짧은 노드를 탐색해오며, 방문 처리합니다.
- 해당 노드를 거쳐 다른 노드로 이동한 거리를 최단 거리 테이블(distance)와 비교하여 갱신합니다.
전체 코드는 이렇습니다.
✅ [ CODE ]
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ 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 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
visited[start] = True
for b, c in graph[start]:
distance[b] = c
for _ in range(n - 1):
now = get_smallest_node()
visited[now] = True
for b, c in graph[now]:
cost = distance[now] + c
if cost < distance[b]:
distance[b] = cost
dijkstra(start)
for i in range(1, n + 1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
☑️ 시간 복잡도
최단 거리 테이블에서 가장 짧은 거리의 노드를 매번 탐색해야 하며, 해당 노드와 연결된 노드를 매번 체크해야 하기 때문에, 노드의 개수 V만큼 시간 복잡도는 $O(V^2)$ 입니다.
노드의 개수가 만 개 이상이 된다면, 문제를 풀어낼 수 없기 때문에 좀 더 개선된 알고리즘 구현 방식을 이용해야 합니다.
📌 우선 순위 큐를 이용한 다익스트라 알고리즘
최단 거리 테이블에서 거리가 가장 짧은 노드를 탐색하는 과정을 우선 순위 큐를 이용하여 시간 복잡도를 개선할 수 있습니다.
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist: # 이미 처리된 적이 있다면, continue로 넘어감
continue
for b, c in graph[now]:
cost = dist + c
if cost < distance[b]:
distance[b] = cost
heapq.heappush(q, (cost, b))- 우선 순위 큐에 출발 노드와 거리 0을 담아줍니다.
- 우선 순위 큐에 아무것도 담겨있지 않을 때까지 반복됩니다.
- 우선 순위 큐에서 최단 거리가 가장 짧은 노드를 꺼냅니다.
- 이미 처리된 적이 있다면, continue로 넘어가고, 그렇지 않다면, 기존 최단 거리와 비교하여 갱신합니다. 우선 순위 큐에 새로 값을 담아줍니다.
전체 코드는 이렇습니다.
✅ [ CODE ]
"""
< 개선된 다익스트라 알고리즘 >
- 최단 거리가 가장 짧은 노드를 선택하는 과정을 우선순위 큐로 대체
"""
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
for i 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로 넘어감
continue
for b, c in graph[now]:
cost = dist + c
if cost < distance[b]:
distance[b] = cost
heapq.heappush(q, (cost, b))
dijkstra(start)
for i in range(1, n + 1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
☑️ 시간 복잡도
heapq는 데이터 삽입 및 삭제 시, 시간 복잡도는 $O(logN)$입니다.
힙에서 데이터를 모두 삽입하는 것은 $O(logN)$의 연산을 N번 반복하므로 $O(NlogN)$입니다. 마찬가지로 삭제하는 것도 $O(NlogN)$입니다. 대략 $2Nlog_2(N)$으로 빅오 표기법에 따라 시간 복잡도는 $O(NlogN)$이 됩니다.
우선 순위 큐로 구현된 다익스트라 구현 방식에서는, 노드를 하나씩 꺼내어 확인하는 반복문은 노드의 개수 V만큼만 반복되며, V번 반복될 때마다 해당 노드와 연결된 간선들을 확인합니다. 간선의 개수 E만큼 연산이 수행될 수 있습니다.
따라서, 우선 순위 큐를 이용하여 구현하면 최악의 경우에도 시간 복잡도는 $O(ElogV)$를 보장합니다.
1. 힙에 E개의 데이터를 모두 삽입하고 삭제하는 것과 유사합니다.. $O(ElogE)$
2. 모든 노드끼리 서로 다 연결되어 있다면, 간선의 개수는 $V^2$입니다. 간선인 E는 항상 $V^2$보다 작거나 같습니다.
즉, $O(logV^2) = O(2logV) = O(logV)$
3. 따라서, 시간 복잡도는 $O(ElogV)$입니다.
시간 복잡도에 대한 이해는 틈날 때마다 다시 읽어보며 익혀야할 것 같다. 소스코드 제대로 기억해두자..!
포스팅 내용에 오류 및 문제가 있는 경우, 댓글로 남겨주시면 감사드리겠습니다.
출처) 이것이 코딩 테스트다 with Python