다익스트라 알고리즘

 

가중치 방향 그래프이므로 graph[a][b] = c or ArrayList<ArrayList<Edge>> 를 사용한다.

거리 비용을 기록해주는 dis 배열을 사용한다.

PriorityQueue를 사용하여 출발 노드를 큐에 넣어주고(1,0) 시작한다.

출발 노드의 거리 비용을 dis[v] = 0 으로 초기화한다. 

 

처음 정점인 1번 노드를 꺼내고 연결되어 있는 노드들을 탐색한다.(2, 3번 노드)

now = 1; nowCost = 0;

1.인접한 2번 노드의 현재 거리 비용(M)이 현재 정점까지의 비용 + 2번으로 가는 비용(12) 보다 크면 2번 노드의 거리 비용으로 바꿔준다.

dis[2] > 0 + 12 참 이므로 dis[2] = 0 + 12 = 12

그리고 해당 정점과 비용을 큐에 넣는다. (2,12) - 1번 정점을 통해서 2번 정점으로 가는데 12라는 비용이 든다.

[[2,12]]

2.인접한 3번 노드의 현재 거리 비용(M)이 현재 정점까지의 비용 + 3번으로 가는 비용(4) 보다 크면 3번 노드의 거리 비용으로 바꿔준다.

dis[3] > 0 + 4 참 이므로 dis[3] = 0 + 4 = 4

그리고 해당 정점과 비용을 큐에 넣는다. (3,4) - 1번 정점을 통해서 3번 정점으로 가는데 4라는 비용이 든다.

[[2,12], [3,4]]

 

그리고 큐에서 다시 거리가 낮은 비용을 가진 노드(3,4) 꺼내고 연결되어 있는 노드들을 탐색한다.(4번 노드)

now = 3; nowCost = 4;

인접한 4번 노드의 현재 거리 비용(M)이 현재 정점까지의 비용(4) + 4번으로 가는 비용(5) 보다 크면 4번 노드의 거리 비용으로 바꿔준다.

dis[4] > 4 + 5 참 이므로 dis[4] = 4 + 5 = 9

그리고 해당 정점과 비용을 큐에 넣는다. (4,9) - 3번 정점을 통해서 4번 정점으로 가는데 9라는 비용이 든다.

[[4, 9], [2, 12]]

 

큐에서 다시 거리가낮은 비용을 가진 노드(4,9) 꺼내고 연결되어 있는 노드들을 탐색한다.(2, 5번 노드)

now = 4; nowCost = 9;

1.인접한 2번 노드의 현재 거리비용(12)이 현재 정점까지의 비용(9) + 2번으로 가는 비용(2) 보다 크면 2번 노드의 거리 비용으로 바꿔준다.

dis[2] > 9 + 2 참 이므로 dis[2] = 9 + 2 = 11

그리고 해당 정점과 비용을 큐에 넣는다. (2, 11) - 4번 정점을 통해서 2번 정점으로 가는데 11이라는 비용이 든다.

[[2, 11], [2,12]]

2.인접한 5번 노드의 현재 거리비용(M)이 현재 정점까지의 비용(9) + 5번으로 가는 비용(5) 보다 크면 5번 노드의 거리 비용으로 바꿔준다.

dis[5] > 9 + 5 참 이므로 dis[5] = 9 + 5 = 14

그리고 해당 정점과 비용을 큐에 넣는다. (5, 14) - 4번 정점을 통해서 5번 정점으로 가는데 14이라는 비용이 든다.

[[2, 11], [2, 12], [5, 14]]

 

큐에서 다시 거리가 낮은 비용을 가진 노드(2, 11) 꺼내고 연결되어 있는 노드들을 탐색한다.(1, 3, 5번 노드)

nowCost - 11 참이 되는 경우가 없음

[[2, 12], [5, 14]]

 

큐에서 다시 거리가 낮은 비용을 가진 노드(2,12) 꺼낸다.

nowCost = 12;

탐색하기 이전에 nowCost 12 > dis[now] 11 이므로 continue; 로 바로 통과한다.

[[5,14]]

 

큐에서 다시 거리가 낮은 비용을 가진 노드(5,14) 꺼내고 연결되어 있는 노드들을 탐색한다(인접 노드 없음)

 

아래와 같이 배열이 완성된다.

 

 

배열 접근 과정

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;
    
    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)){ //1번과 연결되어있는 1,3 / 1,2
                //현재 배열에 들어있는 거리비용이 현재 돌고있는 거리비용보다 크면
                if(dis[ob.vex]>nowCost+ob.cost){
                    //현재 돌고 있는 거리비용이 최소 거리비용이 될 수 있으므로 바꿔준다.
                    dis[ob.vex]=nowCost+ob.cost;
                    //그리고 큐에 해당 정점과 비용을 가지고 있는 Edge 객체를 넣는다.
                    pQ.offer(new Edge(ob.vex, nowCost+ob.cost));
                }
            }
        }
    }

    public static void main(String[] args){
        Main T = 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));
        }
        
        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");
        }
    }
}