[JAVA] 알고리즘 : 그리디- 다익스트라 알고리즘

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
    public int vex; // 정점
    public int cost; // 가중치 비용
    Edge(int vex, int cost){
        this.vex = vex;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge ob){
        return this.cost - ob.cost; // 가중치 오름차순
        // Edge 형의 priority queue를 만들면 작은 값 부터 우선순위
    }
}
class Main{
    static int n, m;
    static int[] dis;
    static ArrayList<ArrayList<Edge>> graph;

    public void solution(int v){
        PriorityQueue<Edge> pq = new PriorityQueue<>(); // cost가 가장 작은 것부터 꺼내짐
        pq.offer(new Edge(v, 0));
        dis[v] = 0;
        while(!pq.isEmpty()){
            Edge tmp = pq.poll(); // 가장 비용이 작은 엣지를 꺼냄
            int now = tmp.vex;
            int nowCost = tmp.cost;

            if(nowCost > dis[now]) continue;

            for(Edge ob: graph.get(now)){
                if(dis[ob.vex] > nowCost + ob.cost){
                    dis[ob.vex] = nowCost + ob.cost; // 작은 비용으로 갱신
                    pq.offer(new Edge(ob.vex, nowCost+ob.cost));
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 정점의 개수
        m = sc.nextInt(); // 간선의 개수
        graph = new ArrayList<ArrayList<Edge>>(); // Edge 객체를 저장할 수 있는 ArrayList
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Edge>());
        }
        dis=new int[n+1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph.get(a).add(new Edge(b,c)); // a번 정점에서 b번 정점으로 가는 비용 c
        }
        T.solution(1); // 1번 정점부터 시작
        for(int i=2; i<=n; i++){
            if(dis[i]!=Integer.MAX_VALUE) System.out.println(i+":"+dis[i]);
            else System.out.println(i+":impossible");
        }
    }
}