우선 순위 큐를 활용해 개선시킨 다익스크라 알고리즘

2022.06.27 - [분류 전체보기] - 최단 경로 - 다익스트라 알고리즘

최단 경로 - 다익스트라 알고리즘

 

최단 경로를 구하는 알고리즘 중 다익스트라 알고리즘을 위의 링크처럼 간단히 구현하면 O(V^2)의 시간 복잡도가 나오기 때문에 노드 개수가 10000개가 넘어가면 위의 코드로는 구현하기가 힘들다.

따라서 매번 최단 거리 테이블을 선형적으로 탐색하는 것이 아니라 우선순위 큐를 활용하여 찾게 되면 O(ElogV)의 시간 복잡도로 구현할 수 있다.

 

개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Node implements Comparable<Node> {
    private int index;
    private int distance;

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

    public int getIndex() {
        return this.index;
    }

    public int getDistance() {
        return this.distance;
    }

    @Override
    public int compareTo(Node node) {
        if (this.distance < node.distance)
            return -1;
        return 1;
    }
}
public class Dijkstra_improved {

    static final int INF = (int) 1e9;
    static int n,m,start;
    static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
    static int[] table = new int[100001];

    public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        table[start] = 0;
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int dist = node.getDistance();
            int now = node.getIndex();
            if (table[now] < dist) continue;
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = table[now] + graph.get(now).get(i).getDistance();
                if (cost < table[graph.get(now).get(i).getIndex()]) {
                    table[graph.get(now).get(i).getIndex()] = cost;
                    pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Node>());
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph.get(a).add(new Node(b, c));
        }

        //테이블을 모두 무한으로 초기화
        Arrays.fill(table, INF);
        dijkstra(start);

        for (int i = 1; i <= n; i++) {
            if (table[i] == INF)
                System.out.println("infinite");
            else
                System.out.println(table[i]);
        }
    }
}