다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 출발 노드와 모든 노드 간의 최단 거리를 찾는 데 사용되는 효율적인 알고리즘 중 하나이다. 이 알고리즘은 양의 가중치를 가진 간선으로 이루어진 그래프에서 사용할 수 있다.

시간 복잡도는 O(ElogV)이다.

 

알고리즘 동작 원리

---

1. 시작점 설정: 최단 경로를 찾을 시작점을 선택한다.
2. 거리 초기화: 시작점을 제외한 모든 정점까지의 거리를 무한대로 설정하고, 시작점의 거리를 0으로 설정한다.
3. 우선순위 큐 초기화: 우선순위 큐를 사용하여 현재까지의 최단 거리를 가진 정점을 방문한다. 시작점을 우선순위 큐에 삽입한다.
4. 최단 경로 갱신: 우선순위 큐에서 가장 최단 거리를 가진 정점을 추출하고, 해당 정점과 이웃한 정점들의 거리를 갱신한다. 새로운 거리가 더 짧으면 해당 정점의 거리를 갱신하고, 우선순위 큐에 새로운 거리를 기반으로 삽입한다. 즉, 방문한 정점의 최단거리가 아니라 방문하게 될 정점의 최단거리를 구하게 된다.
5. 반복 수행: 우선순위 큐가 비어질 때까지 4단계를 반복합니다. 이때, 우선순위 큐에서 추출한 정점은 최단 경로가 확정된 정점으로 간주된다.

 

최단 거리와 최단 경로

import java.util.*;

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE;

    public static void dijkstra(List<List<Node>> graph, int start) {
        int n = graph.size();
        // 각 정점까지의 최단거리
        int[] distance = new int[n];
        Arrays.fill(distance, INF);
        
        // 최단 경로에서 각 정점의 이전 정점
        int[] previous = new int[n];
        Arrays.fill(previous,-1);

        // 방문 여부
        boolean[] visited = new boolean[n];

        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));
        priorityQueue.add(new Node(start, 0));
        distance[start] = 0;
 
        while (!priorityQueue.isEmpty()) {
            Node poll = priorityQueue.poll();
            int curV = poll.vertex;
            // 현재 정점까지의 거리
            int curD = poll.distance;

            if (visited[curV]) {
                continue;
            }

            visited[curV] = true;

            for (Node neighbor : graph.get(curV)) {
                int newDistance = curD + neighbor.distance;
                if (newDistance < distance[neighbor.vertex]) {
                    previous[neighbor.vertex] = curV;
                    distance[neighbor.vertex] = newDistance;
                    // 정점까지의 새로운 거리 값으로 노드를 생성한다.
                    priorityQueue.add(new Node(neighbor.vertex, newDistance));
                }
            }
        }

        // 결과 출력
        System.out.println("최단 경로 결과:");
        for (int i = 1; i < n; i++) {
            List<Integer> path = getPath(previous, i);
            System.out.println("정점 " + i + ": 최단 거리: " + distance[i] + ", 경로: "+ path);
        }
    }

    public static List<Integer> getPath(int[] previous, int destination) {
        List<Integer> path = new ArrayList<>();
        for (int at = destination; at != -1; at = previous[at]) {
            path.add(at);
        }
        Collections.reverse(path);
        return path;
    }

    static class Node {
        int vertex;
        int distance;

        Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
    }
}

 

K번째 최단 거리

import java.util.List;
import java.util.PriorityQueue;

public class KthDijkstra {

    public static int[] kthDijkstra(List<List<Node>> graph, int start, int k) {
        int n = graph.size();
        // 각 정점으로 가는 거리들을 담는 배열
        PriorityQueue<Integer>[] distQueue = new PriorityQueue[n + 1];
        for (int i = 0; i <= n; i++) {
            // k 번째 부터 최단 거리 까지 오름차순 으로 담길 수 있도록 한다.
            distQueue[i] = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
        }

        // 현재 노드에서 출발하여 아직 방문하지 않은 노드까지의 거리 정보를 저장하는 큐
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        distQueue[start].add(0);

        // 탐색 시작
        while (!pq.isEmpty()) {
            Node poll = pq.poll();
            int curV = poll.vertex;
            int curD = poll.distance;

            List<Node> neighbors = graph.get(curV);
            for (Node neighbor : neighbors) {
                int nextV = neighbor.vertex;
                int nextD = neighbor.distance + curD;

                // 저장된 경로가 K개가 안 될 때는 그냥 추가하기
                PriorityQueue<Integer> distanceQ = distQueue[nextV];
                if (distanceQ.size() < k) {
                    distanceQ.offer(nextD);
                    pq.offer(new Node(nextV, nextD));
                /*
                   저장된 경로가 K개이고 현재 가장 큰 값보다 작을 때,
                   k번째 최단 거리를 갱신한다.
                   [15, 10] : 13 => [13, 10]
                */ 
                } else if (distanceQ.peek() > nextD) {
                    distanceQ.poll();
                    distanceQ.offer(nextD);
                    pq.offer(new Node(nextV, nextD));
                }
            }
        }

        // k번째 최단 거리가 담길 배열
        int[] result = new int[n];
        for (int i = 1; i < n; i++) {
            PriorityQueue<Integer> queue = distQueue[i];
            if (queue.size() != k) {
                result[i] = -1;
            } else {
                result[i] = queue.poll();
            }
        }
        return result;

    }
}