# 다익스트라

* 다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.&#x20;
  * 출발 노드와 모든 노드 간의 최단 거리 탐색
  * 에지는 모두 양수
  * O(ElogV) (노드 수 : V, 에지 수 : E)

#### dijkstra 알고리즘의 핵심 이론&#x20;

1. 인접 리스트로 그래프 구현하기
2. 최단 거리 배열 초기화하기
3. 값이 가장 작은 노드 고르기
4. 최단 거리 배열 업데이트하기
5. 과정 3\~4를 반복하여 최단 거리 배열 완성하기&#x20;



### 최단 경로 구하기&#x20;

#### Question - 1753&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FoRPfdN1yApJiHqDrb1Iz%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-09%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%202.48.23.png?alt=media\&token=9908a41a-1cf5-4ad1-b8d3-606d5d68f955)

#### Code

```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class N56_P1753_최단_경로_구하기 {

    public static int node, edge, start;

    public static int distance[];
    public static boolean visited[];

    public static ArrayList<Edge> list[];
    public static PriorityQueue<Edge> pq = new PriorityQueue<Edge>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine()); //주의 !!!!!!!!!11

        distance = new int[node + 1];
        visited = new boolean[node + 1];

        list = new ArrayList[node + 1];
        for (int i = 1; i <= node; i++) {
            list[i] = new ArrayList<Edge>();
        }

        for (int i = 0; i <= node; i++) {
            // 얘는 왜 0부터 해주는 거임 ?
            distance[i] = Integer.MAX_VALUE; // 정수의 최댓값 출력
        }

        // u : 에서
        // v  : 로 가는
        // w : 가중치
        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list[u].add(new Edge(v, w));
        }

        pq.add(new Edge(start, 0));
        distance[start] = 0;

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int CtoV = current.vertex;
            if (visited[CtoV]) continue;
            visited[CtoV] = true;

            for (int i = 0; i < list[CtoV].size(); i++) {
                Edge temp = list[CtoV].get(i);
                int next = temp.vertex;
                int value = temp.value;

                if (distance[next] > distance[CtoV] + value) {
                    distance[next] = value + distance[CtoV];
                    pq.add(new Edge(next, distance[next]));
                }
            }

        }
        for (int i = 1; i <= node; i++) {
            if (visited[i]) {
                System.out.println(distance[i]);
            } else {
                System.out.println("INF");
            }
        }
    }
}

class Edge implements Comparable<Edge> {
    int vertex, value;

    Edge(int vertex, int value) {
        this.vertex = vertex;
        this.value = value;
    }

    public int compareTo(Edge e) {
        if (this.value > e.value) return 1;
        else return -1;
    }
}
j
```

#### Idea

#### reference



### 최소 비용 구하기&#x20;

#### Question - 1916&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FGeTZUsuezJbep0uByRo4%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-09%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%202.49.29.png?alt=media\&token=f5095634-3db8-490e-8abb-386db4a52410)

#### Code

```java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class N57_P1916_최소_비용_구하기 {

    static int node, edge; // country, bus

    static ArrayList<Node>[] list; // 인접 리스트로 그래프 표현하기
    static int[] dist; //최단거리 배열 distance
    static boolean[] visit; // 사용 노드인지 확인 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;

        node = Integer.parseInt(br.readLine());
        edge = Integer.parseInt(br.readLine());

        dist = new int[node + 1];
        visit = new boolean[node + 1];
        Arrays.fill(dist, Integer.MAX_VALUE); // 거리 배열을 충분히 큰 수로 초기화

        list = new ArrayList[node + 1]; //ArrayList<>[]아님 주의
        for (int i = 0; i <= node; i++) { //또 채워줌 0
            list[i] = new ArrayList<Node>();
        }

        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            list[start].add(new Node(end, price));
        }

        st = new StringTokenizer(br.readLine());
        int startCountry = Integer.parseInt(st.nextToken());
        int endCountry = Integer.parseInt(st.nextToken());

        bw.write(dijkstra(startCountry, endCountry) + "\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));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node nowNode = pq.poll();
            int now = nowNode.targetNode;
            if (!visit[now]) {
                visit[now] = true;
                for (Node n : list[now]) {
                    if (!visit[n.targetNode] &&
                            dist[n.targetNode] > dist[now] + n.value) {
                        dist[n.targetNode] = dist[now] + n.value;
                        pq.add(new Node(n.targetNode, dist[n.targetNode]));
                    }
                }
            }
        }
        return dist[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;
    }
}

```

#### Idea

#### reference



### K번째 최단 경로 찾기&#x20;

#### Question - 1854&#x20;

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FmjPCu5uV29ajxZkdx7G4%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-09%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%202.50.18.png?alt=media\&token=23009b46-500f-4aba-ac39-85ec93514107)

#### Code

```java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class N58_P1854_K번째_최단_경로_찾기 {

    static final int INF = 100000000;
    public static void main(String[] args) throws IOException {
        int node, edge, k;
        int[][] w = new int[1001][1001];

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        PriorityQueue<Integer>[] distQueue = new PriorityQueue[node + 1];
        Comparator<Integer> cp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 < o2 ? 1 : -1;
            }
        };
        for (int i = 0; i < node + 1; i++) { // node + 1
            distQueue[i] = new PriorityQueue<Integer>(k, cp);
        }

        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            w[a][b] = c;
        }

        PriorityQueue<tNode> pq = new PriorityQueue<>();
        pq.add(new tNode(1, 0));
        distQueue[1].add(0);
        while (!pq.isEmpty()) {
            tNode u = pq.poll();
            for (int adjNode = 1; adjNode <= node; adjNode++) {
                if (w[u.node][adjNode] != 0) {
                    // 저장된 경로가 k개 안될 떄는 그냥 추가
                    if (distQueue[adjNode].size() < k) {
                        distQueue[adjNode].add(u.cost + w[u.node][adjNode]);
                        pq.add(new tNode(adjNode, u.cost + w[u.node][adjNode]));
                    }

                    // 저장된 경로가 k개이고, 현재 가장 큰 값보다 작을 때만 추가
                    else if (distQueue[adjNode].peek() > u.cost + w[u.node][adjNode]) {
                        distQueue[adjNode].poll();
                        distQueue[adjNode].add(u.cost + w[u.node][adjNode]);
                        pq.add(new tNode(adjNode, u.cost + w[u.node][adjNode]));
                    }
                }
            }
        }

        for (int i = 1; i <= node; i++) {
            if (distQueue[i].size() == k) {
                bw.write(distQueue[i].peek() + "\n");
            } else {
                bw.write(-1 + "\n");
            }
        }

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

class tNode implements Comparable<tNode> {
    int node;
    int cost;

    tNode(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }

    @Override
    public int compareTo(tNode o) {
        return this.cost < o.cost ? -1 : 1;
    }
}

```

#### Idea

#### reference

