[Java] Dijkstra algorithm - (그래프)간선 가중치가 양수

https://blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

https://www.acmicpc.net/problem/1753

1753번: 최단경로

O((V+E)logV)

 

간선 가중치가 음수일 때는 사용할 수 없다.

시작점 k에서 각 정점으로의 거리를 int[] 선언하고, 간선으로 이어진 정점만 거리를 갱신한다.(멀면 INF)

반복해서 가장 가까운 정점을 탐색하고

그 정점에 이어진 정점들로의 거리를 계속해 갱신한다.

 

1) nlgn (아직 명확히 안외워짐)

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

public class dijkstra_nlgn{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static int INF = 999999;
    public static void main(String[] args){
        int n = fs.nextInt(), v = fs.nextInt(), k = fs.nextInt();
        // n : 노드의 개수
        // v : 간선의 개수
        // k : 시작점
        List<List<Node>> list = new ArrayList<>();
        for (int i=0;i<=n;i++) list.add(new ArrayList<>());
        for (int i=0;i<v;i++){
            int from = fs.nextInt(), to = fs.nextInt(), wei = fs.nextInt();
            list.get(from).add(new Node(to, wei));
        }

        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.weight, o2.weight));
        q.add(new Node(k, 0));
        int[] dist = new int[n+1];
        for (int i=0;i<=n;i++) dist[i] = INF;
        dist[k] = 0;

        while (!q.isEmpty()){
            Node curNode = q.poll();

            if (dist[curNode.index] < curNode.weight){
                continue;
            }

            for (int i=0;i<list.get(curNode.index).size();i++){
                Node nextNode = list.get(curNode.index).get(i);

                if (curNode.weight + nextNode.weight < dist[nextNode.index]){
                    dist[nextNode.index] = curNode.weight + nextNode.weight;
                    q.add(new Node(nextNode.index, dist[nextNode.index]));
                }
            }
        }

        for (int i=1;i<=n;i++){
            if (dist[i] == INF) pw.println("INF");
            else pw.println(dist[i]);
        }
        pw.close();
    }

    static class Node {
        int index, weight;

        public Node(int index, int weight){
            this.index = index;
            this.weight = weight;
        }
    }

//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

 

 

2) n^2 (이건 확실히 외웠는데 가끔 tle mle 떠서...)

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

public class dijkstra_n2{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static int n, m, x, INF = 10000000;
    public static void main(String[] args){
        n = fs.nextInt();
        m = fs.nextInt();
        x = fs.nextInt();
        // n:노드 개수 / m:간선 개수 / x:시작점

        int[][] map1 = new int[n+1][n+1];

        for (int[] a : map1){
            Arrays.fill(a, INF);
        }

        for (int i=1;i<=n;i++){
            map1[i][i] = 0;
        }

        for (int i=0;i<m;i++){
            int start = fs.nextInt(), end = fs.nextInt(), wei = fs.nextInt();
            map1[start][end] = wei;
        }

        // int[] pp = dijk(map1);
        // pp : x에서 1~n번 노드까지의 최단 거리

        pw.close();
    }

    static int[] dijk(int[][] dis, int start){
        int[] d = new int[n+1];
        boolean[] v = new boolean[n+1];

        v[start] = true;
        for (int i=1;i<=n;i++){
            d[i] = dis[start][i];
        }

        for (int i=0;i<n-2;i++){
            int next = findIndex(d, v);
            v[next] = true;
            for (int j=1;j<=n;j++){
                if (!v[j] && d[next] + dis[next][j] < d[j]){
                    d[j] = d[next] + dis[next][j];
                }
            }
        }

        return d;
    }

    static int findIndex(int[] d, boolean[] v){
        int min = INF;
        int index = 0;
        for (int i=1;i<=n;i++){
            if (!v[i] && d[i] < min){
                min = d[i];
                index = i;
            }
        }
        return index;
    }

//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}