🚩다익스트라 알고리즘
- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작
현실 세계의 도로는 음의 간선으로 표현되지 않음
- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됨
매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
🚩동작 과정
- 출발 노드를 설정
- 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택(Greedy)
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 위 과정에서 3번과 4번을 반복
🚩다익스트라 알고리즘 특징
- 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
- 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음
한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있음
- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됨
완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 함
🚩힙을 이용한 다익스트라 알고리즘
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용
- 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이요함
- 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용
🚩구현 코드
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정
# 노드의 개수, 간선의 개수 입력
n, m = map(int, input().split())
# 시작 노드 번호 입력 받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)
# 모든 간선 정보 입력받기
for _ in range(m):
# a번 노드에서 b번 노드로 가는 비용은 c
a, b, c = map(int, input().split())
graph[a].append((b,c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
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]:
cost = dist +i[1]
# 현재 노드를 거쳐서 인접한 노드로 이동하는 거리가 거리 테이블 값보다 더 짧은 경우
# 힙에 그 노드까지 가는 값과 노드를 추가
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
# 도달할 수 없는 경우, 거리가 무한이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])
- 우선순위 큐에 들어가는 정보 : ( 비용, 목표 노드) 출발 노드부터 목표 노드까지 비용에 대한 데이터가 힙에 들어간다.
- 힙을 이용한 다익스트라 알고리즘은 방문했는지 체크하는 Checked 리스트가 필요없다.
- 힙에 데이터를 넣을 때, 해당 노드까지 걸리는 전체 길이를 넣는다.
- 최소 힙을 이용해서 목표 노드까지 최소 비용에 인접한 노드들에 대한 정보 graph에 있는 값들을 더해서 최대한 최소의 거리 값들을 갱신한다.
- 시간 복잡도 : O(ElogV) - V:노드 E:간선. 힙의 시간복잡도는 O(logN)
댓글