다익스트라(Dijkstra)

다익스트라(Dijkstra)

 

최단경로 알고리즘

그리디 알고리즘으로 분류 - 매번 가장 비용이 적은 노드를 선택해서 반복

DFS/BFS 의 경우 모든 노드간의 가중치가 같고, 얼마나 적은 수의 노드를 거쳤는지 탐색

다익스트라의 경우 노드간의 가중치가 달라서 얼마나 적은 가중치의 합으로 목적지에 도착했는지 탐색

 

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

시간복잡도 : O(N²)

단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차탐색)한다.

 

우선순위 큐 

우선순위가 가장 높은 데이터를 먼저 삭제

 

시간복잡도 : O(NlogN)

큐에서 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 이상으로 반복되지 않는다.

최대 N개의 간선 데이터를 힙에 넣었다가 다시 빼는 것