다익스트라 (Dijkstra)

💡 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘

• 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
• 음의 간선을 포함할 수 없다. (음의 간선 포함은 벨만-포드 알고리즘 사용)
• 매번 가장 비용이 적은 노드 를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류

알고리즘 작동 원리

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3, 4를 반복한다.

 

알고리즘 구현 방법

 

방법 1. 간단한 다익스트라 알고리즘

• 간단하게 구현할 때 $O(V^2)$의 시간 복잡도를 가진다.
• 전체 노드의 개수가 5,000개 이하일 때 무난하게 사용 가능하지만, 10,000개가 넘어가면 시간 초과가 발생할 수 있다.
• 최단 거리 테이블 배열을 통해서 노드를 선택함.

방법 2. 개선된 다익스트라 알고리즘

• 최악의 경우에도 $O(ElogV)$의 시간 복잡도를 가진다.
• 우선순위 큐를 사용하기 위해 힙(heap)을 사용한다.
• 최단 거리 테이블을 우선순위 큐로 만들어 시간 복잡도를 줄임.