목록2023/10/04 (1)
Rootable의 개발일기
다익스트라(Dijkstra) 알고리즘
사이클 없는 양수 가중치 그래프에서 최단 거리를 구하는 알고리즘 시간 복잡도 : O(ElogV) (V : 노드 수, E : 에지 수) 📌 핵심 이론 🔎 인접 리스트 다익스트라 알고리즘은 인접 행렬보다 시각 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트로 구현하는 것이 좋다. 🔎 최단 거리 배열 초기화 최단 거리 값을 저장하기 위한 배열을 만든다. 출발 노드는 0, 나머지 노드는 매우 큰 값으로 초기화한다. 🔎 값이 가장 작은 노드 고르기 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 따라서, 출발 노드에서 시작하면 된다. 🔎 최단 거리 배열 업데이트 인접 리스트와 최단 거리 배열 값을 비교하여 둘 중 작은 값으로 최단 거리 배열을 갱신한다. Min(출발 노드의 최단 거리 배열의 값 +..
알고리즘
2023. 10. 4. 12:56