다익스트라1 [알고리즘] 다익스트라(Dijkstra) 최단 거리 알고리즘 그래프에서 간선들 사이의 가중치와 방향이 있을 때, 한 정점에서 다른 정점들까지의 최단 거리를 구할 수 있는 알고리즘은 다익스트라, 벨만포드, A* 등이 있고, 모든 정점에서 모든 정점의 최단 거리를 구하는 알고리즘에는 플로이드 워셜 알고리즘이 있다. 해당 알고리즘들을 응용하여 최단 거리를 가지는 경로를 구하는 방법도 있지만, 이 글에서는 다익스트라 알고리즘을 활용하여 최단 거리만 구해보겠다. 먼저 우선순위 큐를 사용하지 않는 최초의 다익스트라 알고리즘은 아래 과정과 같고 O(V2) 의 시간 복잡도를 갖는다. (2중 for 문 구조) 시작 노드 결정 현재 노드를 기준으로 각 노드의 최소 비용을 계산 방문 하지 않은 노드 중 최소 비용의 노드를 선택 선택된 노드를 기준으로 거리 비용을 .. 2022. 4. 11. 이전 1 다음