다익스트라

시작 정점부터 나머지 모든 정점까지의 최단 거리를 구하는 알고리즘.
음의 간선 허용하지 않음. 음 순환 못잡음.
그리디의 성격 알고리즘임.

즉, 매번 방문한 노드를 기준으로 인접한 노드들을 살펴보며, 현재 방문 노드가 가진 시작정점부터 방문노드까지의 최단경로 + 방문노드에서 인접노드까지의 거리를 살펴보고, 기존의 최단 경로 테이블을 갱신시킬 수 있다면 최단 경로 테이블을 갱신한다.

방문 노드와 인접한 노드를 찾기 위해, 인접행렬을 쓰기보다는 인접리스트를 사용하자. 그러면, 불필요한 시간을 줄일 수 있다.

현재까지 구한 최단 경로 테이블 내에서 아직 방문하지 않은 가장 짧은경로를 갖는 노드를 선택함.

이 과정을 매번 최단 경로 테이블을 살펴보며 선형적으로 탐색하면너무 시간이 오래 걸림. 그래서 우선순위큐를 쓴다.

참고로, 다익스트라는 그리디 알고리즘이라서 굳이 방문여부 테이블을 저장할 필요가 없다. 어차피 재방문해도 갱신 못시킨다.
-> 다익스트라 문제들을 풀어봤을 때, 방문 여부 테이블을 안만드는게 시간 복잡도가 더 좋았다.

    static int dijkstra(int s) {
        int[] table = new int[V + 1];
        Arrays.fill(table, Integer.MAX_VALUE);
        table[s] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> {
            return n1.cost - n2.cost;
        });
        pq.add(new Node(s, 0));

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            // 여기가 바로, 그리디로 최종적으로 결정된 영역임.

            for (Node node : graph[curNode.n]) {
                int next = curNode.cost + node.cost;
                if (next < table[node.n]) {
                    table[node.n] = next;
                    pq.add(new Node(node.n, next));
                }
            }
        }

        int maxValue = 0;
        for (int i = 1; i <= V; i++) {
            if (i == s) continue;
            maxValue = Math.max(maxValue, table[i]);
        }
        return maxValue;
    }