다익스트라(Dijkstra) 알고리즘 추천 문제
다익스트라
bfs,dfs는 가중치가 있을 때 최단거리를 표현하기 어려운데, 다익스트라 알고리즘을 사용하면 가능하다. 하나의 정점에서 모든 정점까지의 최단거리를 각각 구해주는 알고리즘이다. 즉 최단 경로 탐색 알고리즘으로써 플로이드 와샬은 음의 간석을 표현할 수 있지만 다익스트라는 불가능하다.
시작노드 와 도착노드 사이의 최단거리를 찾을 때 유용하게 사용된다.
너비우선탐색인 bfs를 기본으로 한다.
동작과정
초기에 시작할 정점을 정해서 인접한 간선 들을 배열에 저장하고 갈 수 없는 간선은 INF 로 초기화 한다. 이후에 초기 시작 정점에서 가장 작은 비용을 선택하여 또 다시 배열을 인접한 부분과 이전의 값과 비교하여 최단거리를 계속해서 갱신해나간다.
시간 복잡도
우선 순위 큐 를 사용하지 않으면 O( | V | ^{2})이지만 우선 순위 큐에 기반한 알고리즘은 O( | E | + | V | \log | V | )로 최단 경로 알고리즘 중 점근적으로 가장 빠른 알고리즘이다. |