목록다익스트라 (1)

영원히 남는 기록, 재밌게 쓰자

다익스트라 알고리즘

한 노드에 대해서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다.음수 가중치(음의 간선, 음의 값)이 없어야 한다는 특징이 있다.초기 모델은 가장 비용이 싼 정점을 구하기 위해 모든 정점을 탐색하는 구조이기 때문에 시간 복잡도가 O(n^2)이지만개선된 모델인 우선 순위 큐를 사용하는 모델의 경우 O(MlogN)까지 줄일 수 있다. (M은 간선, N은 정점)다익스트라 알고리즘은 기본적으로 그리디 알고리즘과 다이나믹 프로그래밍 기법을 사용한다. 다익스트라 알고리즘의 과정크게 알고리즘의 동작과정은 다음과 같다. 출발지 노드를 기준으로 시작한다. (출발지 노드로 부터 다른 모든 노드까지 최단 거리를 구하는 알고리즘이기 때문)아직 방문하지 않은 정점 중에 출발지에서 가장 짧은 정점을 찾아서 방문한다.해당 ..
Algorithm 2024. 5. 5. 23:04
이전 Prev 1 Next 다음