다익스트라 ( Dijkstra )

다익스트라 알고리즘은 가중치가 존재하는 그래프에서 사용되고
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.

다익스트라 알고리즘은 그리디 알고리즘의 일종으로,
매번 방문하지 않은 정점들 중에서 가장 최단 거리가 짧은 정점을 선택해
방문하며 최단 거리를 갱신한다.

다익스트라 알고리즘의 구현 방법은 총 4단계로 나눌 수 있다.

• 1. 최단거리 배열을 만들고 출발 정점은 0으로,
     이외의 정점들은 최단 거리를 무한대로 초기화한다.

     for (int i = 0 ; i < Distance.length ; i++) {
     	Distance[i] = Integer.MAX_VALUE;
     }
     Distance[start_Node] = 0;

     
     
• 2. 시작 정점에서 방문하지 않은 정점들 중에서 최단 거리가 가장 짧은 정점을 선택
     
     

• 3. 해당 정점과 인접한 정점들의 최단 거리를 갱신.
     새로운 최단거리가 기존의 최단거리보다 더 짧으면 해당 정점을 다음에 방문할 정점으로 선택

     // 현재 노드와 연결된 인접 리스트 노드를 최소 거리로 업데이트
     for (int i  = 0; i < Graph[curr_vertex].size(); i++) {
         Node tmp = Graph[curr_vertex].get(i);
         int next = tmp.Vertex;
         int cost = tmp.Cost;
     
         // 최소 거리로 Distance 업데이트
         if (Distance[next] > Distance[curr_vertex] + cost) {
            Distance[next] = Distance[curr_vertex] + cost;
            pq.add(new Node(next, Distance[next]));
         }
     }

* 4. 모든 정점을 방문할 때 까지 2-3단계를 반복

주의 !
다익스트라 알고리즘은 음수가중치가 존재할 경우 사용이 불가능하다.

---

자바로 다익스트라 알고리즘을 구현할 때는 우선순위 큐(Priority Queue)를 이용하는것이 효율적이다.

우선순위큐는 원소를 우선순위에 따라 자동으로 정렬해주는 자료구조이므로,
다익스트라 알고리즘에서는 현재까지 방문하지 않은 정점에서
가장 최단거리가 짧은 정점을 빠르게 찾을 수 있다.

---

난 다익스트라 알고리즘을 구현할 때

ArrayList<Node> Graph[];
PriorityQueue<Node> pq = new PriorityQueue<>();

클래스를 인접리스트로 구현하고,
때문에 우선순위 큐 또한 클래스를 자료형으로 받는다.

이 경우에는 한 가지 문제점이 생기는데,
우선순위에 따라 자동으로 정렬해주는 우선순위 큐가
Node class의 무엇을 기준으로 정렬을 수행해야하는지 모른다는 것이다.

때문에 이를 해결하기 위해 따로 compareTo 함수를 Override 하는 작업이 필요하다.

    static class Node implements Comparable<Node> {

        int Vertex; // 정점
        int Cost; // 비용

        Node(int Vertex, int Cost) {
            this.Vertex = Vertex;
            this.Cost = Cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.Cost - o.Cost; // Cost가 더 작은 값이 우선 순위
        }

    }

---

다익스트라 예제
[ 백준 ] 최단경로

	static ArrayList<Node> Graph[];
    static boolean Visited[];

    // 거리 배열
    static int Distance[];

    static int V = 5; // 노드의 개수
    static int E = 6; // 간선의 개수
    static int K = 1; // 시작 노드

    public static void main(String[] args) {

        Graph = new ArrayList[V + 1];
        Visited = new boolean[V + 1];
        Distance = new int[V + 1];

        for (int i = 0; i < Graph.length; i++) {
            Graph[i] = new ArrayList<>();
        }

        // Integer.MAX_VALUE (거의 무한 값) 으로 초기화 시켜주어야함
        // 최소값을 기준으로 점점 업데이트해야하기 때문
        for (int i = 0; i < Distance.length; i++) {
            Distance[i] = Integer.MAX_VALUE;
        }

        // 인접리스트 값 입력
        Graph[1].add(new Node(2, 2));
        Graph[1].add(new Node(3, 3));
        Graph[1].add(new Node(4, 1));
        Graph[2].add(new Node(3, 4));
        Graph[2].add(new Node(4, 2));
        Graph[5].add(new Node(1, 1));

        // 최소값을 가장 먼저 뽑아내는 우선순위 큐
        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(K, 0));
        Distance[K] = 0;

        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            int curr_vertex = curr.Vertex;

            // 이미 방문한 적이 있는 노드는 다시 큐에 넣지 않음
            if (Visited[curr_vertex] == true) {
                continue;
            }

            // 방문 처리
            Visited[curr_vertex] = true;

            // 현재 노드와 연결된 인접 리스트 노드를 최소 거리로 업데이트
            for (int i = 0; i < Graph[curr_vertex].size(); i++) {
                Node tmp = Graph[curr_vertex].get(i);
                int next = tmp.Vertex;
                int cost = tmp.Cost;

                // 최소 거리로 Distance 업데이트
                if (Distance[next] > Distance[curr_vertex] + cost) {
                    Distance[next] = Distance[curr_vertex] + cost;
                    pq.add(new Node(next, Distance[next]));
                }
            }
        }

        for (int i = 1; i <= V; i++) {
            if (Visited[i] == true) {
                System.out.println(Distance[i]);
            } else {
                System.out.println("INF");
            }
        }


    }

    static class Node implements Comparable<Node> {

        int Vertex;
        int Cost;

        Node(int Vertex, int Cost) {
            this.Vertex = Vertex;
            this.Cost = Cost;
        }

        // 1  : 크다 x > 0, 현재 개체가 매개 변수 개체보다 큰 경우
        // -1 : 작다 x < 0, 현재 개체가 매개 변수 개체보다 작은 경우
        // 0  : 같다 x == 0, 현재 개체와 매개 변수 개체가 같은 값일 경우
        @Override
        public int compareTo(Node o) {
        /*if (this.Cost > o.Cost)
            return 1;
        else
            return -1;*/
            return this.Cost - o.Cost;
        }

    }

출력
0
2
3
1
INF