14. 다익스트라 알고리즘
알고리즘 공부
2019. 10. 3.
다익스트라 알고리즘 (데이크스트라) 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 (single source shortest path problem) 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 방향 그래프, 무방향 그래프 모두 상관없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다. 에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은의 시간 복잡도를 가졌다. 이후 우선순위 큐(힙 트리)등을 이용한 더욱 개선된 알고리즘이 나오며, 의 시간복잡도를 가지게 되었다.의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데의..
