Dijkstra

정의

• 가중치가 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘

특징

• 음수 가중치가 없는 그래프에서 가능
• 매번 최단 거리인 정점 선택
• 우선수위 큐를 사용하여 구현하며, 시간복잡도는 O(E logV)

코드

구현

public void dijkstra() {
    Queue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(start, 0));
    dist[start] = 0;

    while (!queue.isEmpty()) {
        Node cur = queue.poll();

        if (dist[cur.v] < cur.w) {
            continue;
        }

        for (Node next : graph.get(cur.v)) {
            if (dist[next.v] > dist[cur.v] + next.w) {
                dist[next.v] = dist[cur.v] + next.w;
                queue.add(new Node(next.v, dist[next.v]));
            }
        }
    }
}

public class Node implements Comparable<Node> {
    int v;
    int w;

    public Node(int v, int w) {
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Node o) {
        return this.w - o.w;
    }
}

경로 추적

public void dijkstra() {
    Queue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(start, 0));
    int[] prev = new int[n + 1];
    dist[start] = 0;

    while (!queue.isEmpty()) {
        Node cur = queue.poll();

        if (dist[cur.v] < cur.w) {
            continue;
        }

        for (Node next : graph.get(cur.v)) {
            if (dist[next.v] > dist[cur.v] + next.w) {
                dist[next.v] = dist[cur.v] + next.w;
                prev[next.v] = cur.v;
                queue.add(new Node(next.v, dist[next.v]));
            }
        }
    }
}

public class Node implements Comparable<Node> {
    int v;
    int w;

    public Node(int v, int w) {
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Node o) {
        return this.w - o.w;
    }
}

특정 정점을 반드시 통과하는 최단 경로

public void solve() {
    int[] d1 = dijkstra(1);
    int[] d2 = dijkstra(v1);
    int[] d3 = dijkstra(v2);
}

public int[] dijkstra(int start) {
    Queue<Node> queue = new PriorityQueue<>();
    queue.add(new Node(start, 0));
    int[] dist = new int[N + 1];
    Arrays.fill(dist, 987654321);
    dist[start] = 0;

    while (!queue.isEmpty()) {
        Node cur = queue.poll();

        if (dist[cur.v] < cur.w) {
            continue;
        }

        for (Node next : graph.get(cur.v)) {
            if (dist[next.v] > dist[cur.v] + next.w) {
                dist[next.v] = dist[cur.v] + next.w;
                queue.add(new Node(next.v, dist[next.v]));
            }
        }
    }

    return dist;
}

public class Node implements Comparable<Node> {
    int v;
    int w;

    public Node(int v, int w) {
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Node o) {
        return this.w - o.w;
    }
}