[알고리즘]-다익스트라 알고리즘(Dijkstra Algorithm)

개념

최단경로 탐색 알고리즘이다.

메커니즘

1. BFS알고리즘을 이용해 방문하지 않은 노드 중 가중치가 적은 노드 선택
2. 초기 노드와 다른 노드 사이의 가중치를 구한다
3. BFS중 더 작은 가중치가 나오면 최단경로로 설정한다.
4. BFS가 끝나면 각 노드의 최단경로가 나온다.

구현 방식

• 인접 행렬
• 우선순위 큐

시간복잡도

• 인접행렬 : O(V^2)
• 우선순위 큐 : O((V+E)logV)

요약

• 우선순위 큐 방식이 시간적으로 효율적이다.
• 코드 보면서 이해하기 (그래프나)