[백준 : JAVA] 1753 최단경로

풀이

다익스트라(Dijkstra) 알고리즘을 활용하여 최단 경로를 구하는 코드입니다. 다익스트라 알고리즘은 시작 노드에서부터 다른 모든 노드까지의 최단 경로를 찾는 데 사용됩니다.

public class Main {
	// 간선 정보를 저장하기 위한 클래스
	static class Edge implements Comparable<Edge>{
	    int end, weight;

	    public Edge(int end, int weight){
	        this.end = end;
	        this.weight = weight;
	    }
		// 가중치 값에 따라 정렬
	    @Override
	    public int compareTo(Edge o) {
	        return weight - o.weight;
	    }
	}
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    // v : 노드의 개수, e : 간선의 개수, k : 시작 노드 번호
    static int v,e,k;
    static List<Edge>[] list;
    // 시작 노드에서부터 해당 노드까지의 최단 거리를 저장하는 배열
    static int[] minEdge;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(br.readLine());
        list = new ArrayList[v + 1];
        minEdge = new int[v + 1];

        Arrays.fill(minEdge, Integer.MAX_VALUE);

        for(int i = 1; i <= v; i++){
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0 ; i < e; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            list[start].add(new Edge(end, weight));
        }

        StringBuilder sb = new StringBuilder();
        dijkstra(k);
        for(int i = 1; i <= v; i++){
            if(minEdge[i] == Integer.MAX_VALUE) sb.append("INF\n");
            else sb.append(minEdge[i] + "\n");
        }

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

    private static void dijkstra(int start){
    	// 정렬
       PriorityQueue<Edge> queue = new PriorityQueue<>();
       boolean[] visited = new boolean[v + 1];
       queue.add(new Edge(start, 0));
       minEdge[start] = 0;

       while(!queue.isEmpty()){
           Edge curEdge = queue.poll();
           int cur = curEdge.end;

           if(visited[cur]) continue;
           visited[cur] = true;

           for(Edge e : list[cur]){
               if(minEdge[e.end] > minEdge[cur] + e.weight){
                   minEdge[e.end] = minEdge[cur] + e.weight;
                   queue.add(new Edge(e.end, minEdge[e.end]));
               }
           }
       }
    }
}

minEdge[] = {INF, INF, INF, INF, INF}; // 모든 값을 무한대로 저장(최대값)
-> {0, INF, INF, INF, INF}; // 시작 지점을 0으로 지정
-> {0, 2(0+2), 3(0+3), INF, INF} // 1에서 갈 수 있는 노드들의 값 변경
-> {0, 2, 3, 7(2+5), INF} // 2에서 4로 갈때는 2+5<INF 이므로 변경
-> {0, 2, 3, 7, INF} // 3에서 4로 갈때는 3+6<7을 만족하지 않으므로 변경 x

입력 값
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6