[알고리즘 문제]가중치 방향 그래프 - 다익스트라 알고리즘

▷ 문제

아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로
그램을 작성하세요. (경로가 없으면 Impossible를 출력한다)

* 입력
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연
결정보와 거리비용이 주어진다.
* 출력
1번 정점에서 각 정점으로 가는 최소비용을 2번 정점부터 차례대로 출력하세요.

▷ 입력 예시

6 9

1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5

▷ 출력 예시

2 : 11
3 : 4
4 : 9
5 : 14
6 : impossible

▷ 풀이

import java.util.*;

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;
    }
}

class Main{
    static int n, m;
    static ArrayList<ArrayList<Edge>> graph;
    static int[] dis; // 1부터 각 정점까지의 거리
    
    public void solution(int v){
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        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 main = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        graph = new ArrayList<ArrayList<Edge>>();

        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 = kb.nextInt();
            int b = kb.nextInt();
            int c = kb.nextInt();
            graph.get(a).add(new Edge(b, c));
        }

        kb.close();
        main.solution(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");                
            }
        }
    }
}

▷ 메모

• 다익스트라 알고리즘(Dijkstra)은 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘이다. 기본적으로 Greedy와 DP(동적 프로그래밍)기법을 사용하며 PriorityQueue를 이용하면 O(ElogV)까지 시간복잡도를 줄일 수 있다.