다익스트라 알고리즘 (Dijkstra)

다익스트라(Dijkstra) 최단 경로 알고리즘

• 최단 경로 탐색 알고리즘이다.
• 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
• 음의 간선을 포함할 수 없다. 
• 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 적합하다.
  • 인공위성 GPS 소프트웨어 

 

다익스트라 알고리즘은 그리디 알고리즘 / 다이나믹 프로그래밍으로 분류

• 단계마다 가장 비용이 적은 노드를 선택한다. (그리디)
• 최단 거리는 여러 개의 최단 거리로 이루어져있으므로, 최단거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용한다. (DP)

 

최단 거리 테이블

• 최단 거리 테이블은 각 노드까지의 현재 최단 거리 정보를 저장한다.
• 더 짧은 경로(비용이 더 적은 경로)를 찾은 경우 갱신한다.

 

동작과정

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

 

 

 

 

 

 

 

 

 

 

 

• [Step 7] 우선순위 큐에서 원소를 꺼냅니다. 6번 노드에서 출발하는 경로가 없으므로 무시합니다.
• [Step 8] 우선순위 큐에서 원소를 꺼냅니다. 3번 노드는 이미 방문했으므로 무시합니다.

 

 

특징

• 단계마다 방문하지 않았으면서 가장 비용이 적은 노드를 선택하여 방문한다.
• 한 번 방문하여 계산을 끝낸 노드의 최단 거리는 고정된다. Fix
• 최단 거리 테이블에 각 노드까지의 최단 거리 정보를 저장한다.

 

 

 

시간복잡도

최단 거리가 가장 짧은 노드를 선택하는 방법에 따라 달라진다.

 

1. 리스트

• 단계마다 모든 노드를 선형탐색하여, 방문하지 않았으면서 최단 거리가 가장 짧은 노드를 선택한다.

• 한 번 모든 노드를 선형탐색할 때 : O(V)
• 전체 시간 복잡도 : O(V^2)

 

2. 우선순위 큐 : 우선순위가 높은 데이터를 먼저 삭제하는(꺼내는) 자료구조 

• 단계마다 우선순위 큐에서 원소를 꺼내어, 방문하지 않은 노드인 경우 방문한다.
• 방문한 노드와 인접한 노드를 비용과 함께 우선순위 큐(최소 힙)에 삽입한다. 
• 비용에 따라 노드가 우선순위 큐에 정렬된다.

• 힙 : 트리 구조 (대부분 표준 라이브러리 지원)

 

 

 

 

 

출처

https://www.youtube.com/watch?v=acqm9mM1P6o [동빈나]

https://blog.naver.com/ndb796/221234424646 [안경잡이개발자 동빈나]

23. 다익스트라(Dijkstra) 알고리즘

https://www.youtube.com/watch?v=F-tkqjUiik0 [한빛미디어, 동빈나]