다익스트라 최단거리 알고리즘

class Node implements Comparable<Node>{
    private int index;
    private int distance;

    Node(int index, int distance){
        this.index=index;
        this.distance=distance;
    }
    public int getIndex(){
        return this.index;
    }
    public int getDistance(){
        return this.distance;
    }

    //거리가 짧은 것이 높은 우선순위를 가지도록
    @Override
    public int compareTo(Node other){
        if(this.distance< other.distance){
            return -1;
        }
        return 1;
    }
}

Node 클래스를 만들고 Comparable를 implements하여 compareTo를 override한다.
거리가 짧은 것이 높은 우선순위를 가지도록 구현해준다.

  
public static final int INF=(int)1e9;
public static int n,m, start;
public static ArrayList<ArrayList<Node>>graph=new ArrayList<ArrayList<Node>>();
  
public static int[]d=new int[100001];

public static void dijkstra(int start){

        PriorityQueue<Node> pq=new PriorityQueue<>();

        pq.offer(new Node(start,0));

        d[start]=0;

        while(!pq.isEmpty()){
            //가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
            Node node=pq.poll();
            int dist= node.getDistance();
            int now=node.getIndex();

            //현재 노드가 이미 처리 된 적 있는 노드라면 무시
            if(d[now]<dist) continue;
            //현재 노드와 연결된 다른 인접한 노드들을 확인
            for(int i=0;i<graph.get(now).size();i++){
                int cost=d[now]+graph.get(now).get(i).getDistance();
                if(cost<d[graph.get(now).get(i).getIndex()]){
                    d[graph.get(now).get(i).getIndex()]=cost;
                    pq.offer(new Node(graph.get(now).get(i).getIndex(),cost));
                }
            }
        }
    }

우선 순위 큐로 가장 최단 거리가 짧은 노드를 바로 꺼낼 수 있게 해준다.
첫 시작 노드의 거리는 0으로 하여 큐에 넣어 준다.
현재 노드 거리 배열에도 0으로 넣어준다.


큐가 비어있을 때까지 반복하는데
가장 최단 거리가 짧은 노드를 꺼내고


그 노드가 이미 처리 된 적이 있는 노드라면 무시한다.
이 것으로 인해 visited 배열은 없어도 된다.


처리되지 않은 노드라면
bfs처럼 현재 노드와 연결된 다른 인접한 노드들을 확인해 준다.
새로운 cost를 만들어 주도 원래의 값보다 작다면 변경을 해준 뒤, 큐에 넣어 준다.

 public static void main(String [] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());

        //그래프 초기화
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<>());
        }
        //모든 간선 정보를 입력 받기
        for(int i=0; i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            //a번의 노드에서 b번 노드로 가는 비용이 c라는 의미
            graph.get(a).add(new Node(b,c));
        }

        //최단 거리 테이블을 모두 무한으로 초기화
        Arrays.fill(d,INF);

        dijkstra(start);

        //모든 노드로 가기 위한 최단 거리를 출력
        for(int i=1;i<=n;i++){

            //도달할 수 없는 경우, 무한이라고 출력
            if(d[i]==INF){
                System.out.println("INFINITY");
            }
            //도달할 수 있는 경우 거리를 출력
            else System.out.println(d[i]);
        }
    }       

여기서 중요한 것은 그래프를 초기화 해주는 것과, 그래프의 비용을 추가하는 것, 최단 거리 테이블을 모두 무한으로 초기화하는 것이다.

다익스트라를 공부한게 거의 처음인데, bfs와 비슷하면서도 약간 더 어려운 것 같다.

중요한 것은 최소인지 꺼내고 확인하고 갱신하고 반복인 것 같다.

다음에는 문제를 풀어봐야겠다.