다익스트라(Dijkstra) 알고리즘
우선순위 큐와 힙 자료구조를 이용한 알고리즘이다.
가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단 경로를 return 하는 알고리즘이다.
만약 A→F로 가장 뻐룬 경로를 생각해보자. 만약 모든 간선의 비용이 일정하기에 BFS를 활용해 가장 빠른 경로를 찾을 수 있다. 반면에 가중치가 존재한다면, 그 가중치를 계산해 가장 빠른 경로를 찾을 수 있는게 다익스트라 알고리즘이다.
•
비가중치 → BFS
•
가중치 → 다익스트라
흐름
1.
우선순위 큐에 시작 노드 추가
반복구간
a.
우선순위가 가장 높은 노드 추출
b.
방문여부 확인
c.
비용 업데이트
d.
현재 노드와 연결된 노드 우선순위 큐에 추가
2.
목적지에 기록된 비용 반환
원리만 이해한다면, 쉽게 짤 수 있는 알고리즘
General 코드
import heapq
def dijkstra(graph, start, final, n):
costs = {}
pq = []
heapq.heappush(pq, (0, start))
while pq:
cur_cost, cur_v = heapq.heappop(pq)
if cur_v not in costs:
costs[cur_v] = cur_cost
for cost, next_v in graph[cur_v]:
next_cost = cur_cost + cost
heapq.heappush(pq, (next_cost, next_v))
return cost[final]
Python
복사