'다익스트라' 태그의 글 목록

[알고리즘] 그래프 최단거리 - 다익스트라(Dijkstra) 알고리즘

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다. 다익스트라(Dijkstra) 알고리즘출발 노드와 모든 노드 간의 최단 거리 탐색 (출발 노드와 도착 노드, 두 노드만이 아님)에지(가중치)는 모두 양수여야 한다시간 복잡도는 O(E * logV)그리디 알고리즘- 접근 방법그래프를 인접 행렬, 인접 리스트로 구현할 수 있지만 일반적인 경우에서 인접 리스트가 더 빠름, 하지만 상황에 따라 달라짐- 인접 행렬 O(V^2) - 밀집 그래프에 유리, 연결 노드 확인하는 데 O(1)- 인접 리스트 O(E * log V) - 희소 그래프에 유리, 연결 노드 확인하는 데 O(연결된 간선의 수)최단 거리 배열을 초기화 (최댓값으로 모두 채우기)거리 배열에 출발 노드 인덱스에 0..

문제 및 이론 정리/Algorithm 2024.12.07

hail2y.log

다익스트라 1

티스토리툴바