[Algorithm]Dijkstra 최단 경로 알고리즘
틀린 부분이 있다면 언제든지 댓글 남겨주세요!
최단 거리 알고리즘
- Dijkstra 알고리즘
- 그래프에서 여러 개의 노드가 있을 때 특정 노드에서 다른 노드로 가는 각각의 최단 경로 (0보다 적안 값을 가지는 간선이 없어야 함) = greedy 알고리즘(가장 비용이 적은 노드 선택)
- 최단경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단거리를 1차원 리스트에 계속 갱신 = 최단 거리 테이블
- 출발 노드에서 다른 모든 노드로 가는 최단거리는 '무한' = 999,999,999(=약 10억) = 1e9 = 주로 int(1e9)로 초기화
- 최단 거리가 같은 경우 주로 더 작은 번호의 노드를 선택
- 최단 거리를 갱신할 수 있는 최단 거리가 없는 경우 최단 거리 테이블을 갱신하지 않음
- 이미 방문처리된 노드는 최단 거리의 값이 바뀌지 않으므로 확인할 필요 없음
- 간단한 dijkstra 알고리즘
= 시간 복잡도 O(v^2) (V=노드의 개수)
[ 과정 ]
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택
- 해당 노드(현재 해당 노드까지의 최단 거리는 정해져 있음)를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블 갱신
- 선택(3번)과 갱신(4번) 반복
- 한 단계당 하나의 노드에 대한 최단거리를 찾는 것(=매 단계마다 1차원 리스트의 모든 원소를 순차 탐색)
- 알고리즘 종료 후 테이블에는 각 노드까지의 최단거리가 저장되어 있음
# 간단한 dijkstra 알고리즘 = O(v^2)의 시간 복잡도 (V=노드의 개수)
import sys
input=sys.stdin.readline
INF=int(1e9)
node, line=map(int, input().split()) # [입력] 노드 개수, 간선 개수
start=int(input()) # [입력] 시작 노드 번호
graph=[[] for i in range(node+1)] # 각 노드에 연결되어 있는 노드에 대한 정보 담는 리스트 생성
visited=[False]*(node+1) # 방문처리 리스트, 노드 인덱스에 맞춰서 접근하기 위해 +1 개 생성
distance=[INF]*(node+1) # 최단 거리 테이블 최대값으로 초기화
for _ in range(line): # [입력] 간선 정보 > 그래프 생성
a, b, c=map(int, input().split()) # a->b 노드로 가는 간선 거리가 c
graph[a].append((b, c)) # a노드와 연결된 (b노드, 거리c) 튜플을 리스트에 추가
def get_smallest_node(): # 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 반환
minn=INF # 최단거리 초기화
index=0 # 최단거리 노드 인덱스 저장할 변수
for i in range(1, node+1): # 노드 1~n 인덱스까지
if distance[i] < minn and not visited[i]: # 방문하지 않은 노드 중 현재 간선 보다 짧은 경우
minn=distance[i]
index=i
return index
def dijkstra(start):
distance[start]=0 # 시작 노드 간선 거리 초기화, 자기 자신까지의 거리이므로 0
visited[start]=True # 현재 노드 방문처리
for j in graph[start]: # 시작 노드의 경우
distance[j[0]]=j[1] # 시작 노드와 연결된 노드별 간선 거리 저장
for i in range(node-1):
now=get_smallest_node() # 현재 남은 노즈 중 최단거리를 가진 노드 가져옴
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, node+1): # [결과] 모든 노드까지의 최단거리 출력
if distance[i] == INF: # 최단거리가 없는 경우
print("Infinity")
else: # 최단거리 출력
print(distance[i])- 개선된 dijkstra 알고리즘
= 시간 복잡도 O(E log V) (E=간선의 개수, V=노드의 개수)
- 전체 노드의 개수가 10,000개를 넘어가면 시간 복잡도가 증가하기 때문에 간단한 dijkstra알고리즘을 사용하는 경우 효율성 면에서 좋은 점수를 받기 어려움
- 선형적으로 탐색했던 방법과 달리, Heapq(min heap, 값이 낮은 데이터가 먼저 삭제)을 바탕으로 하는 우선순위 큐를 이용하여 알고리즘 구현
* 우선순위 큐 구현시 heapq 대신 list를 사용해도 되지만 힙의 삽입 시간 복잡도는 O(log N), 삭제 O(log N)인 반면 리스트는 삽입 시간 복잡도가 O(1), 삭제 O(N)이다
* 최소 힙을 최대 힙(max heap, 값이 큰 데이터가 먼저 삭제)처럼 사용하기 위해 우선순위에 해당하는 값에 (-)를 붙여서 힙에 넣었다가 뺄 때 다시 (-)를 붙여 원래 값으로 돌리는 테크닉을 이용하기도 함
- 기본 원리는 간단한 dijkstra와 같음, 단계별로 방문하지 않은 노드 중 간선이 가장 짧은 노드를 선택하기 위해 최소힙을 사용
출처: 이것이 코딩테스트다 나동빈 저