참조: https://www.youtube.com/watch?v=611B-9zk2o4&t=1155
참조: https://freedeveloper.tistory.com/384
다익스트라 알고리즘
- 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘
- 특정한 하나의 정점으로 가는 최단 경로를 탐색한다.
- 단, 음의 간선을 포함할 수 없다.
- 인공위성 GPS 소프트웨어 등에 가장 많이 사용된다.
다익스트라 알고리즘 동작 과정
- 그래프를 준비하고 출발 노드를 설정한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번을 처리한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 4번을 처리한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 2번을 처리한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 5번을 처리한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 3번을 처리한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 6번을 처리한다.
다익스트라 알고리즘 특징
-
그리디 알고리즘: 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.
-
단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.
-> 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다. -
다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다.
-> 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 한다.
다익스트라 알고리즘 구현 방법
선형 탐색 구현 방법
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
v, e = map(int, input().split()) # 노드, 간선 갯수 입력받기
start = int(input()) # 시작 노드 번호를 입력받기
graph = [[] for i in range(v+1)] # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
visited = [False] * (v+1) # 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
distance = [INF] * (v+1) # 최단 거리 테이블을 모두 무한으로 초기화
# 모든 간선 정보를 입력받기
for _ in range(e):
a, b, c = map(int, input().split())
graph[a].append((b, c)) # a번 노드에서 b번 노드로 가는 비용이 c
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def GetSmallestNode():
minValue = INF
index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
for i in range(1, v+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 i in graph[start]:
distance[i[0]] = i[1]
# 시작 노드를 제외한 전체 (v-1)개의 노드에 대해 반복
for i in range(v-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, v+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])- 성능 분석
총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색 해야한다.
따라서 전체 시간 복잡도는 O(V^2)이다.
일반적으로 전체 노드의 갯수가 5000개 이하라면 이 코드로 문제를 해결할 수 있다.
우선순위 큐 구현 방법
import sys
import heapq
input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
INF = int(1e9)
distance = [INF] * (n+1)
graph = [[] for _ in range(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, node = heapq.heappop(q)
if distance[node] < dist: # 큐에서 뽑아낸 거리가 이미 갱신된 거리보다 클 경우(=방문 완료) 무시
continue
for next in graph[node]:
cost = distance[node] + next[1] # 시작 -> node 거리 + node->node의 인접 노드 거리
if cost < distance[next[0]]:
distance[next[0]] = cost
heapq.heappush(q, (cost, next[0]))
Dijkstra(start)
for i in range(1, len(distance)):
if distance[i] == INF:
print('도달할 수 없음')
else:
print(distance[i])- 성능 분석
해당 노드와 연결된 노드들만 탐색하므로 최악의 경우라도 총 간선의 개수인 E만큼 반복한다.
따라서 하나의 간선에 대해 걸리는 시간 복잡도는 O(logV)이며, 최악의 경우 O(ElogV)이다.
