최단경로

다익스트라 개념

• 최단경로 알고리즘
  (시작 정점에서 모든 정점의 최단거리 구하기)
• 유방향성
• 음의 가중치 불가 (음의 가중치는 밸만포드로 해야 함)
• 프림과 유사함

MST : 크루스칼 , 프림
-> 음의 가중치 가능 (무방향)
최단경로 : 다익스트라
-> 음의 가중치 불가능 (유방향)

예시

프림과 유사하다
단 다익스트라는 (여태까지 온 비용 + 해당 노드 연결비용 VS 원래 비용)를 비교해서 min으로 갱신한다

논리

연결된(선택된) 애들의 팔이 닿는(인접한) 애들 중
시작 노드로부터의 거리가 가장 가까운 애를 선택한다

구현 코드

Priority Queue 사용 버전

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//백준 골드5 1753 최단경로
//PQ 다익스트라 연습
public class BJ_G5_1753_최단경로 {

	static class Edge implements Comparable<Edge>{
		int node, weight;
		public Edge(int node, int weight) {
			this.node = node;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge o) {
			return weight-o.weight;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int V =  Integer.parseInt(st.nextToken());
		int E =  Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(br.readLine()) - 1;
		int dist[] = new int[V]; //시작 정점부터 i번 정점까지의 최단거리
		Arrays.fill(dist, Integer.MAX_VALUE);
		ArrayList<ArrayList<Edge>> adjList = new ArrayList<>();
		for(int i=0; i<V; i++) adjList.add(new ArrayList<>());
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken())-1;
			int to = Integer.parseInt(st.nextToken())-1;
			int weight = Integer.parseInt(st.nextToken());
			adjList.get(from).add(new Edge(to, weight)); //유방향성
		}
		
		//pq는 시작노드->해당노드까지의 거리를 담는다
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] v = new boolean[V];
		pq.add(new Edge(K, 0));
		dist[K] = 0;	
		while(!pq.isEmpty()) {
			//시작노드부터 거리가 가장 가까운 애 poll	
			Edge curr = pq.poll();
			
			//일단 뽑히면 가장 가까운 거리로 온거니까 그다음 부턴 얘를 다시 살펴볼 필요가 없음
            if (v[curr.node]) continue;
            v[curr.node] = true;
            
            //다른 방법으로 간 경로가 더 가까울 수도 있으니 방문체크 X
			for(Edge e : adjList.get(curr.node)) {
				int d = dist[curr.node] + e.weight;
				//아직 확정(방문)되지 않은 애면, 현재 선 연결된 애들 중 기존 정보보다 저 가까운 애가 있으면 큐에 넣기
				if(d<dist[e.node]) {  
					//해당 노드부터 d까지의 거리 갱신
					dist[e.node] = d;
					//방문 안한 애일 수도 있으니 pq에 넣음
					pq.add(new Edge(e.node, d));
				}
			}
		}
		for(int d : dist) System.out.println(d!=Integer.MAX_VALUE?d:"INF");
	}
}

적용 예시

적용 사진

관련 문제

백준 골드5 1753 최단경로