[백준 1753] 최단경로(Java) 다익스트라

문제

https://www.acmicpc.net/problem/1753

 

 

알고리즘

다익스트라 (우선순위 큐 사용)

 

 

풀이

이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이 할 수 있다.

먼저 모든 노드의 거리를 무한으로 초기화 한다.

그리고 우선순위 큐를 사용하여 간선의 거리가 짧은 것부터 나오도록 해주어 시작점부터 다른 노드까지의 최소 거리를 구한다.

 

 

코드

package com.company;


import java.io.*;
import java.util.*;

public class Test_dijstra {
    static int V,E;
    static int start;

    static int[] dist;

    static List<POINT>[] graph;
    static final int INF = 987654321;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        V= Integer.parseInt(st.nextToken());
        E= Integer.parseInt(st.nextToken());

        start = Integer.parseInt(bf.readLine());
        dist =new int[V+1];
        graph = new ArrayList[V+1];

        for(int i=1; i<=V; i++){
            graph[i] = new ArrayList<>();
        }

        Arrays.fill(dist, INF);

        //리스트에 그래프 정보를 초기화
        for(int i=1; i<=E; i++){
            st= new StringTokenizer(bf.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int dis = Integer.parseInt(st.nextToken());
            graph[from].add(new POINT(dis,to));
        }

        dijstra(start);

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=V; i++){
            if(dist[i]==INF){
                sb.append("INF"+"\n");
            }else{
                sb.append(dist[i]+"\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static void dijstra(int s){
        PriorityQueue<POINT> pq = new PriorityQueue<>();
        dist[s] = 0;
        pq.add(new POINT(0, s));
        while(!pq.isEmpty()){
            int current = pq.peek().to;
            int dis = pq.peek().dis;
            pq.poll();
            if(dis> dist[current]) continue;

            for(int i=0; i<graph[current].size(); i++){
                int next = graph[current].get(i).to;
                int nextDis = dis + graph[current].get(i).dis;
                if(nextDis < dist[next]){
                    dist[next] = nextDis;
                    pq.add(new POINT(nextDis,next));
                }
            }
        }
    }

    public static class POINT implements  Comparable<POINT>{
        int dis;
        int to;

        public POINT(int dis, int to) {
            this.dis = dis;
            this.to = to;
        }

        //양수-> 오름 차순
        //음수-> 내림차순
        @Override
        public int compareTo(POINT o) {
            return dis-o.dis;
        }
    }
}

 

 

다익스트라 개념

https://m.blog.naver.com/ndb796/221234424646