다익스트라(dijkstra) 알고리즘

다익스트라는 임의의 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 

작동원리는 임의의 한 점에서 다른 한 점까지 최단 거리를 갱신해주는 것이다.

최단 거리는 여러 정점을 타고 수차례 갱신될 수 있다. 

 

이 설명은 그림이 좀 많이 필요한데 시간이 없다. 내일 시험이라서 나중에 수정해서 올리겠다. (여유가 생기면)

혹시 그럴 일은 없겠지만 내 블로그 애청자가 있다면 쪽지보내면 직접 설명 해주겠다.

 

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

1753번: 최단경로

package practice2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

class info implements Comparable<info>{
	int vertex,val;

	public info(int vertex, int val) {
		this.vertex = vertex;
		this.val = val;
	}

	@Override
	public int compareTo(info o) {
		return Integer.compare(this.val, o.val);
	}
}

public class boj1197 {
	static int N, M, S, answer;
	static int D[];
	static ArrayList<ArrayList<info>> list;
	static PriorityQueue<info> pq;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] s = in.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		S = Integer.parseInt(in.readLine());
		
		D = new int[N+1];
		pq = new PriorityQueue<info>();
		
		list = new ArrayList<>();
		for(int i =0; i<=N;i++)list.add(new ArrayList<info>());
		
		for (int i = 0; i < M; i++) {
			s = in.readLine().split(" ");
			int from = Integer.parseInt(s[0]);
			int to = Integer.parseInt(s[1]);
			int val = Integer.parseInt(s[2]);
			list.get(from).add(new info(to,val));
		}
		
		Arrays.fill(D, Integer.MAX_VALUE);
		D[S]=0;
		pq.add(new info(S,0));
		
		while(!pq.isEmpty()) {
			int cur = pq.peek().vertex;//현재 정점
			int dist = pq.peek().val;//현재 정점까지의 비용
			pq.poll();
			
			if(dist<D[cur])continue;//이미 갱신이 된 노드라면 넘어간다.
			//pq에는 넣은 순서대로 나오지 않기 때문에 나중에 나온 값이 이미 갱신이 되어버렸을 수도 있다.
			//뿐만 아니라 다른 정점에서  D[cur]로 가는 것에 대해 값을 갱신을 해버렸을 경우도 있기 때문에 이와 같은 구조로 가지치기를 해야한다.
			//이 노드까지 오는 값이 갱신이 되었다고 가정해보자. 어디를 경유해서 현재 cur노드에 온것이다.
			//그 값이 이cur과 dist가 들어 갈 때의 값보다 더 작아진 상태면 무조건 현재의 D[cur]에 적혀있는 경로로 오는게 제일 짧다.
			//다익스트라는 갱신된 노드에 대해서는 다시 갱신을 하지 않는다.
			
			for(int i=0; i<list.get(cur).size(); i++) {
				int nextVertex = list.get(cur).get(i).vertex;//다음 정점
				int val = list.get(cur).get(i).val;//다음 정점으로 가는 비용
				if(D[nextVertex]>dist+val) {//다음 정점 가는것보다 현재정점까지 오는 비용에서 다음정점으로 가는 비용을 합친게
					//더 크다면
					D[nextVertex]=dist+val;//비용 갱신
					pq.add(new info(nextVertex, dist+val));//그리고 갱신된 정점을 다시 pq에 집어넣기
				}
			}
		}
		for(int i =1; i<=N;i++) {
			if(D[i]==2147483647)System.out.println("INF");
			else System.out.println(D[i]);
		}
	}
}