[알고리즘] 최단거리 알고리즘 다익스트라 Java 참고 코드

그래프가 주어졌을 때, 한 노드에서부터 다른 모든 노드들까지의 최단 거리를 구하는 것을 Single Point Shortest Path 라고 한다. Single Point Shortest Path 를 구하는 알고리즘에는 벨만포드 알고리즘 과 다익스트라 알고리즘 이 있다. 다익스트라 알고리즘은 우선순위 큐로 구현시 O(ElogE) 시간복잡도를 갖는다. 벨만포드 알고리즘 보다 더 빠르다. 구현 방식은 최단 거리 계산이 완료된 정점을 계속해서 추가하는 방식으로 BFS, 프림 알고리즘과 유사하다.

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

package 최단경로.다익스트라.최단경로;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] strs = br.readLine().split(" ");
        int V = Integer.parseInt(strs[0]);
        int E = Integer.parseInt(strs[1]);
        int K = Integer.parseInt(br.readLine());
        
        int[] dist = new int[V + 1];
        boolean[] check = new boolean[V + 1];
        for (int i = 1; i <= V; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        
        ArrayList<Edge>[] arr = (ArrayList<Edge>[]) new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) {
            arr[i] = new ArrayList<Edge>();
        }
        
        for (int i = 0; i < E; i++) {
            String[] nums = br.readLine().split(" ");
            
            int u = Integer.parseInt(nums[0]);
            int v = Integer.parseInt(nums[1]);
            int w = Integer.parseInt(nums[2]);
            
            arr[u].add(new Edge(v, w));
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        dist[K] = 0;
        pq.offer(new Node(K, 0));
        
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            
            if (check[cur.v]) continue;
            check[cur.v] = true;
            
            for (int i = 0; i < arr[cur.v].size(); i++) {
                Edge next = arr[cur.v].get(i);
                
                if (dist[next.e] > dist[cur.v] + next.w) {
                    dist[next.e] = dist[cur.v] + next.w;
                    pq.offer(new Node(next.e, dist[next.e]));
                }
            }
        }
        
        for (int i = 1; i <= V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(dist[i]);
            }
        }
    }
}

class Edge {
    int e, w;

    public Edge(int e, int w) {
        super();
        this.e = e;
        this.w = w;
    }
}

class Node implements Comparable<Node> {
    int v, d;

    public Node(int v, int d) {
        super();
        this.v = v;
        this.d = d;
    }

    @Override
    public int compareTo(Node o) {
        return this.d - o.d;
    }
}

최단 경로의 길이뿐만 아니라 실제 경로를 구하려고 한다면 각 정점에 대해서 최단 경로상에 이전 노드를 저장하는 배열을 추가로 처리하면 된다.

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

package 최단경로.다익스트라.최소비용_구하기2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
            
        int[] dist = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        int[] prev = new int[N + 1];
        boolean[] check = new boolean[N + 1];
        
        ArrayList<int[]>[] arr = (ArrayList<int[]>[]) new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = new ArrayList<int[]>();
        }
        
        for (int i = 0; i < M; i++) {
            String[] nums = br.readLine().split(" ");
            
            int s = Integer.parseInt(nums[0]);
            int e = Integer.parseInt(nums[1]);
            int w = Integer.parseInt(nums[2]);
            
            arr[s].add(new int[] {e, w});
        }
        
        String[] nums = br.readLine().split(" ");
        int source = Integer.parseInt(nums[0]);
        int destination = Integer.parseInt(nums[1]);
        
        dist[source] = 0;
        prev[source] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(source, 0));
        
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            
            if (check[cur.v]) continue;
            check[cur.v] = true;
            
            for (int i = 0; i < arr[cur.v].size(); i++) {
                int[] edge = arr[cur.v].get(i);
                int next = edge[0];
                int weight = edge[1];
                
                if (dist[next] > dist[cur.v] + weight) {
                    dist[next] = dist[cur.v] + weight;
                    prev[next] = cur.v;
                    
                    pq.offer(new Node(next, dist[next]));
                }
            }
        }
        
        System.out.println(dist[destination]);
        
        int index = destination;
        Stack<Integer> st = new Stack<>();
        st.push(destination);
        
        while(prev[index] != 0) {
            index = prev[index];
            st.push(index);
        }
        
        System.out.println(st.size());
        while(!st.isEmpty()) {
            System.out.printf("%d ", st.pop());
        }
    }
}

class Node implements Comparable<Node> {
    int v, d;

    public Node(int v, int d) {
        super();
        this.v = v;
        this.d = d;
    }

    @Override
    public int compareTo(Node o) {
        return this.d - o.d;
    }
}