Algorithm/개념 정리

[개념 정리] 다익스트라 Dijkstra

다익스트라란?최단 경로 탐색 중 하나로 시작점을 기준으로 모든 정점에 대해 최단 경로를 찾음단! 가중치는 음수이면 안된다! -> 왜?? 참고 인접 행렬로 표현된 그래프의 경우 시간 복잡도 O(n^2) -> 낮은 가중치 탐색해야함우선순위 큐 사용하여 시간 복잡도 O(mlog n)까지 낮출 수 있음 → 개선된 다익스트라 알고리즘기본 코드(우선순위 큐 사용, 다익스트라 메서드만 작성)static void dijkstra(int start) { dp[start] = 0; PriorityQueue pq = new PriorityQueue(); pq.offer(new Node(start, 0)); while (!pq.isEmpty()) { ..