[코테 알고리즘] 다익스트라 (Dijkstra) 알고리즘

최단거리를 구하는 다익스트라(Dijkstra) 알고리즘

---

시작노드와 나머지 노드 간의 최단거리를 탐색하는
알고리즘을 다익스트라 알고리즘이라고 한다.
(단, 이때 엣지가 모두 양수여야한다.)

🕑 시간복잡도: O(V^2) (V:노드수, E:간선수)
[ O(ElogV): 우선순위 큐 이용시 ]

다익스트라(Dijkstra)와 우선순위 큐(Priority Queue)

---

다익스트라 알고리즘은 '우선순위 큐(Priority Queue)'로 구현하며,
'우선순위 큐(Priority Queue)'란 데이터가 새롭게 들어올 때마다 '자동으로 정렬'하는 큐를 말한다.
정렬 기준은 Node클래스의 'compareTo() 함수'를 통해 설정할 수 있다.

다익스트라(Dijkstra) 코드 구현

---

⚠️ 선택노드가 다시 선택되지 않도록 방문여부를 체크할 배열이 필요하다.

1. 인접리스트 초기화한다.
2. 방문배열을 초기화한다.
3. 최단거리배열 초기화한다.
4. 우선순위 큐에 시작노드를 넣고 최단경로배열 0으로 처리
5. 우선순위 큐에서 자동정렬된 데이터를 뽑고 방문처리한다.
6. D[선택노드]+가중치 와 D[타깃노드] 를 비교, 작은 값으로 업데이트하고, 우선순위 큐에 넣는다.
7. 방문하지 않은 노드 중 5번 6번 반복
8. 우선순위 큐가 비면 종료

<백준 알고리즘, 1916번>

🎯 우선순위 큐를 이용하면 설정한 기준에 의해 자동정렬되어 poll()만 하면 간편하게 원하는 기준의 값을 뽑을 수 있다.

import java.io.*;
import java.util.*;
class Main {
    static int N, M;
    static List<Node>[] A; // 인접리스트
    static int[] D; // 최단거리배열
    static boolean[] visited; // 방문배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine()); // 도시 수
        M = Integer.parseInt(br.readLine()); // 버스 수
        A = new ArrayList[N+1];
        D = new int[N+1];
        visited = new boolean[N+1]; // 방문배열 초기화
        Arrays.fill(D, Integer.MAX_VALUE); // 최단거리배열을 큰 수로 초기화하기

        for(int i = 0; i <= N; i++) { 
            A[i] = new ArrayList<Node>();
        }

        for(int i = 0; i < M; i++) { // 인접리스트 초기화
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            A[start].add(new Node(end, weight)); // 중요 **
        }
        st = new StringTokenizer(br.readLine());
        int startIndex = Integer.parseInt(st.nextToken());
        int endIndex = Integer.parseInt(st.nextToken());

        bw.write(dijkstra(startIndex, endIndex) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위큐로 정렬
        pq.offer(new Node(start, 0)); // 우선순위 큐에 시작 노드를 넣고
        D[start] = 0;
        while(!pq.isEmpty()) { // 우선순위 큐가 비면 종료
            Node nowNode = pq.poll(); // 자동 정렬된 데이터 뽑기
            int now = nowNode.targetNode;
            if(!visited[now]) { // 방문을 안했다면
                visited[now] = true; // 방문처리
                for(Node n : A[now]) {
                    if(!visited[n.targetNode] && D[n.targetNode] > D[now] + n.value) { // D[선택노드] + 비용 < D[타깃 노드] 일때,
                        D[n.targetNode] = D[now] + n.value; // 갱신
                        pq.add(new Node(n.targetNode, D[n.targetNode])); // 갱신한 정보를 우선순위 큐에 넣는다
                    }
                }
            }
        }
        return D[end];
    }
}
class Node implements Comparable<Node> {
    int targetNode;
    int value;
    Node(int targetNode, int value) {
        this.targetNode = targetNode;
        this.value = value;
    }
    @Override
    public int compareTo(Node o) { 
        return value - o.value; // 정렬기준
    }    
}