[Algorithm] 다익스트라 알고리즘

해당 글은 바킹독님의 강의를 참고해서 정리한 글입니다.

다익스트라 알고리즘이란 ?

하나의 시작점으로부터 다른 모든 정점까지의 최단 거리 (최소 비용)를 구하는 알고리즘. 단, 음수의 가중치를 가지는 간선이 존재하면 사용할 수 없다. 해당 경우는 벨만 포드 알고리즘 사용할 것 !

cf. 플루이드-워셜 알고리즘 : 모든 정점 쌍 사이의 최단 거리

다익스트라 알고리즘은 매 단계마다 도달할 수 있는 정점 중에서 시작점으로부터의 거리가 가장 가까운 정점을 구해서 그 거리를 확정하는 방식으로 동작한다.

일종의 그리디 알고리즘

적어도 현재 갈 수 있는 정점 중에서 가장 가까운 거리의 정점까지의 거리는 확정 가능하기 때문

우선순위 큐를 이용한 다익스트라 알고리즘

🤔 왜 우선순위 큐 ?

원소의 추가 및 삭제가 가능하고, 최솟값을 빠르게 찾을 수 있는 자료구조이기 때문이다.

1. 우선순위큐에 (0, 시작점) 추가
2. 우선순위큐에서 거리가 가장 작은 원소를 선택하고, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 PASS
3. 원소가 가리키는 정점을 $v$라고할 때, $v$와 이웃한 정점들에 대해 최단거리테이블 값보다 $v$를 거쳐가는 것이 더 작을 경우, 최단거리테이블의 값을 갱신하고, 우선순위큐에 (거리, 이웃한 정점 번호) 추가한다.
   • 이렇게 안하면 걍 dfs 돌리는 것 ..
4. 큐가 빌 때까지 2, 3번 과정을 반복한다.