다익스트라자 알고리즘

가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하기, 경로가 없으면 impossible 출력

 

첫째 줄에는 정점의 수 N과 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다.

 

입력
6 9
1 2 12 <- 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

 

음수가 아닌 가중치 방향그래프에서 다익스트라자 알고리즘을 이용해서 최소 거리비용을 찾는 문제

 

정점의 길이만큼 dis 배열을 만들어서 큰 값을 넣어두고, 처음에 넣어둔 큰 값보다 작은 값이 그 정점에 도달하는 거리비용이면 dis 배열의 값을 갱신한다, 우선순위 큐를 사용하면 N*N의 시간복잡도를 NlogN으로 개선할수 있다

 

풀이방법

 

먼저 정점의 정보를 저장할 클래스를 만든다 , 각 정점은 정점의 번호와 그 정점까지 가는데 걸리는 비용으로 이루어진다

우선순위 큐에 넣을때 작은 비용부터 오름차순으로 나오게 Comparable을 써서 비용을 기준으로 오름차순 정렬한다

class Edge implements Comparable<Edge>{
    int vex; //정점
    int cost; //비용
    Edge(int vex, int cost){
        this.vex = vex;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        // 오름차순으로 정렬
        return this.cost - o.cost;
    }
}

한 정점에 연결된 다른 정점을 for문으로 탐색하기 위해 정점을 원소로 가지는 ArrayList를 담을 수 있는 ArrayList를 만든다

    static  ArrayList<ArrayList<Edge>> graph = new ArrayList<ArrayList<Edge>>();
    for (int i =0; i <= n; i++) graph.add(new ArrayList<Edge>());
    for (int i =0; i < m; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            //a번 정점에서 b번 정점까지 가는데 c만큼 비용이 든다는걸 저장
            graph.get(a).add(new Edge(b,c));
        }

 

정점까지의 거리를 저장할 dis배열을 만들고, 큰 값으로 초기화한다

dis = new int[n+1];
Arrays.fill(dis,Integer.MAX_VALUE);

 

다익스트라자 알고리즘으로 최소거리를 구하는 함수

pq에서 꺼내지는 값은 방문 비용이 가장 작은 값이다

 for문을 돌면서 정점들을 탐색하며 dis값보다 now 노드를 거쳐서 정점에 도달하는 거리비용이 작으면 dis값을 갱신한다

    public void Solution(int v){
        //꺼내지는 기준은 edge를 만들때 해둔 오름차순을 기준으로
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        //시작하는 노드 1을 넣어주고
        pq.offer(new Edge(1,0));
        //당연히 시작 노드까지 가는 비용은 0이다
        dis[v] = 0;
        while (!pq.isEmpty()){
            Edge tmp = pq.poll();
            int now = tmp.vex;
            int nowCost = tmp.cost;
            //nowCost가 dis[now] 보다 크면, 비용이 정점을 더 거쳐서 비용이 더 들 수 밖에 없으니 건너뛴다
            if (nowCost > dis[now]) continue;
            //now와 연결된 정점들을 순회하면서 최소 비용을 탐색
            for (Edge ob : graph.get(now)){
                //현재 정점과 연결된 정점의 비용을 기존 연결된 정점의 비용이 dis 보다 작으면, 처음에 dis가 max로 초기화되었기에
                //방문한 정점이면 작아질수 밖에 없음
                 if (dis[ob.vex] > nowCost + ob.cost){
                     dis[ob.vex] = nowCost + ob.cost;
                     //pq에 현재 정점과 연결된 정점의 비용을 기존 연결된 정점의 비용과 합쳐서 넣음
                     pq.offer(new Edge(ob.vex, ob.cost + nowCost));
                 }
            }
        }
    }

전체 코드

import java.util.*;

class Edge implements Comparable<Edge>{
    int vex; //정점
    int cost; //비용
    Edge(int vex, int cost){
        this.vex = vex;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        // 오름차순으로 정렬
        return this.cost - o.cost;
    }
}


class Main{

    static  int n;
    static  ArrayList<ArrayList<Edge>> graph;
    static int[] dis; //최소거리를 구하기 위해서 사용하는 배열

    public void Solution(int v){
        //꺼내지는 기준은 edge를 만들때 해둔 오름차순을 기준으로
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        //시작하는 노드 1을 넣어주고
        pq.offer(new Edge(1,0));
        dis[v] = 0;
        while (!pq.isEmpty()){
            Edge tmp = pq.poll();
            int now = tmp.vex;
            int nowCost = tmp.cost;
            //nowCost가 dis[now] 보다 크면, 비용이 정점을 더 거쳐서 비용이 더 들 수 밖에 없으니 건너뛴다
            if (nowCost > dis[now]) continue;
            //now와 연결된 정점들을 순회하면서 최소 비용을 탐색
            for (Edge ob : graph.get(now)){
                //현재 정점과 연결된 정점의 비용을 기존 연결된 정점의 비용이 dis 보다 작으면, 처음에 dis가 max로 초기화되었기에
                //방문한 정점이면 작아질수 밖에 없음
                 if (dis[ob.vex] > nowCost + ob.cost){
                     dis[ob.vex] = nowCost + ob.cost;
                     //pq에 현재 정점과 연결된 정점의 비용을 기존 연결된 정점의 비용과 합쳐서 넣음
                     pq.offer(new Edge(ob.vex, ob.cost + nowCost));
                 }
            }


        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        graph = new ArrayList<ArrayList<Edge>>();
        //0~n 번까지 Edge를 넣을수 있는 ArrayList를 만들어두고 1번부터 N번까지 N개를 사용함, 0번부터 넣어주니 0 <= N
        for (int i =0; i <= n; i++) graph.add(new ArrayList<Edge>());
        dis = new int[n+1];
        //dis 배열에 최대값을 넣어서 초기화, 나중에 값이 변하지 안았으면 도달 불가능한 정점
        Arrays.fill(dis,Integer.MAX_VALUE);
        for (int i =0; i < m; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            //a번 정점에서 b번 정점까지 가는데 c만큼 비용이 든다는걸 저장
            graph.get(a).add(new Edge(b,c));
        }

        T.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");
        }

    }
}