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