다익스트라 알고리즘(Dijkstra's algorithm) - 우선순위 큐

다익스트라 알고리즘(Dijkstra's algorithm) - 우선순위 큐

 

우선순위 큐 구현에는 전 게시물에서 사용한 인정 행렬 구현을 수정해 사용한다.

https://stdio-han.tistory.com/85

다익스트라 알고리즘(Dijkstra's algorithm) - 인접 행렬

 

[설명]

이전에 사용한 인접행렬 방식과 다른 부분을 위주로 설명한다.

 

 

// (a,b) -> a[0] - b[0] 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

먼저 우선순위 큐를 선언해준다.

 

 

  // 시작노드값 초기화
        Dist[v] = 0;
        Check[v] = true;
        pq.add(new int[]{v, 0});

시작 노드값 초기화시 우선순위 큐 pq에 시작노드와 가중치를 선언해준다.

 

 

        // 인접한 노드 Dist 갱신
        for (int i = 0; i < N; i++) {
            if (!Check[i] && Graph[v][i] != INF) { // 방문하지 않은 노드 && INF 가 아닌경우
                Dist[i] = Graph[v][i]; //값 갱신
                pq.add(new int[]{Graph[v][i], i});
            }
        }

인접한 노드에 대한 정보도 큐에 입력해준다.

 

 

while (!pq.isEmpty()) {
            // 노드 최소값 찾기
            int[] curr = pq.poll();
            int min_index = curr[1];

            // 다른 노드를 거쳐 가는 것이 더 비용이 적은지 확인
            Check[min_index] = true; // 방문한 노드 true
            for (int j = 0; j < N; j++) {
                if (!Check[j] && Graph[min_index][j] != INF) {
                    if (Dist[min_index] + Graph[min_index][j] < Dist[j]) {
                        Dist[j] = Dist[min_index] + Graph[min_index][j];
                        pq.add(new int[]{Dist[j], j});
                    }
                }
            }

            // 결과값 출력
            for (int j = 0; j < N; j++) {
                if(Dist[j] == INF) System.out.print("INF" + "\t");
                else System.out.print(Dist[j]+"\t");
            }
            System.out.println("");

        }

최소 노드값을 찾을 때 우선순위 큐에서 꺼낸다.

min_index = curr[1] 로 선언해준다. 이때 curr[0] 은 노드의 가중치, curr[1] 은 노드번호이다.

 

 

[코드]

 

import java.io.*;
import java.util.*;

public class Main {

    static int INF = Integer.MAX_VALUE;
    static int N, E; // 노드의 개수, 간선의 개수
    static int[][] Graph; // 노드들간의 가중치를 저장할 변수
    static int[] Dist; // 최단 거리를 저장할 변수
    static boolean[] Check; // 해당 노드를 방문했는지 체크할 변수
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken()); // 노드의 개수
        E = Integer.parseInt(st.nextToken()); // 간선의 개수
        Graph = new int[N][N];
        Dist = new int[N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 인접행렬 모든 값 INF 로 초기화
                Graph[i][j] = INF;
            }
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            Graph[u][v] = Graph[v][u] = cost; // 양방향 간선
        }

        dijkstra(0);

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dijkstra(int v) {
        // (a,b) -> a[0] - b[0] 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        Dist = new int[N];
        Check = new boolean[N];

        // Dist 값 초기화
        for (int i = 0; i < N; i++) {
            Dist[i] = INF;
        }

        // 시작노드값 초기화
        Dist[v] = 0;
        Check[v] = true;
        pq.add(new int[]{v, 0});

        // 결과값 출력
        for (int i = 0; i < N; i++) {
            if(Dist[i] == INF) System.out.print("INF" + "\t");
            else System.out.print(Dist[i]+"\t");
        }
        System.out.println("");

        // 인접한 노드 Dist 갱신
        for (int i = 0; i < N; i++) {
            if (!Check[i] && Graph[v][i] != INF) { // 방문하지 않은 노드 && INF 가 아닌경우
                Dist[i] = Graph[v][i]; //값 갱신
                pq.add(new int[]{Graph[v][i], i});
            }
        }

        // 결과값 출력
        for (int i = 0; i < N; i++) {
            if(Dist[i] == INF) System.out.print("INF" + "\t");
            else System.out.print(Dist[i]+"\t");
        }
        System.out.println("");

        while (!pq.isEmpty()) {
            // 노드 최소값 찾기
            int[] curr = pq.poll();
            int min_index = curr[1];

            // 다른 노드를 거쳐 가는 것이 더 비용이 적은지 확인
            Check[min_index] = true; // 방문한 노드 true
            for (int j = 0; j < N; j++) {
                if (!Check[j] && Graph[min_index][j] != INF) {
                    if (Dist[min_index] + Graph[min_index][j] < Dist[j]) {
                        Dist[j] = Dist[min_index] + Graph[min_index][j];
                        pq.add(new int[]{Dist[j], j});
                    }
                }
            }

            // 결과값 출력
            for (int j = 0; j < N; j++) {
                if(Dist[j] == INF) System.out.print("INF" + "\t");
                else System.out.print(Dist[j]+"\t");
            }
            System.out.println("");

        }
    }
}

 

[결과]

 

[정리]

입력값이 커져 그래프의 크기가 커지면 커질수록 우선순위 큐가 인접행렬 방식을 사용했을때보다 시간상 이점이 발생한다.