다익스트라 알고리즘

• 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘.
• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산함.
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작.
• 다익스트라 알고리즘 동작 과정
  1. 출발 노드를 설정함.
  2. 최단 거리 테이블을 초기화함.
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택함.
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신함.
  5. 위 과정에서 3번과 4번을 반복함.
• 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음.
• 처리 과정에서 더 짧은 경로를 찾으면 갱신함.

• 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장됨.

 

• 다익스트라 알고리즘을 구현하는 방법
  1. 간단한 구현 방법
     • 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인 (순차 탐색) 함.
     • 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 함. 따라서, 전체 시간 복잡도는 O(V^2)
  2. 개선된 구현 방법
     • 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용.
     • 다익스트라 알고리즘이 동작하는 기본 원리는 동일.
       • 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용.
       • 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용.

• 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)

 

[참고]

www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8