다익스트라

다익스트라 알고리즘

하나의 노드에서 모든 노드로 갈 수 있는 최단거리를 구할 수 있다.

구현

1. 시작 노드를 정한다
2. 출발 노드와 연결된 각 노드의 최소비용을 정한다
   while
3. 방문 하지 않은 노드 중 가장 적은 비용 선택
4. 해당 노드를 거쳐서 특정 노드로 가는 경우 고려해 최소 비용 갱신
   현재 노드를 기준으로 도착지 노드의 거리가 현재 노드까지 거리 + 다음 노드의 가중치 보다 크면 거리를 갱신해준다.

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

public class 다익스트라 {

	static class Node implements Comparable<Node>{
		int end, w;
		
		public Node(int end, int w) {
			this.end = end;
			this.w = w;
		}
		
		@Override
		public int compareTo(Node o) {
			return this.w-o.w;
		}
	}
	
	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		
		int start = Integer.parseInt(br.readLine());
		ArrayList<Node>[] list = new ArrayList[v+1];
		
		for(int i=1; i<=v; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0; i<e; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			list[a].add(new Node(b,c));
		}
		dist = new int[v+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		check = new boolean[v+1];
		
		dijkstra(list, start);
		
		for(int i = 1; i<dist.length; i++) {
			if(dist[i] == Integer.MAX_VALUE) System.out.println("INF");
			else System.out.println(dist[i]);
		}
	}

	static int[] dist;
	static boolean[] check;
	static void dijkstra(ArrayList<Node>[] list, int start) {
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.add(new Node(start, 0));
		dist[start] = 0;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			if(check[cur.end]) continue;
			check[cur.end] = true;
			
			for(Node node : list[cur.end]) {
				if(dist[node.end] > dist[cur.end]+node.w) {
					dist[node.end] = dist[cur.end]+node.w;
					q.add(new Node(node.end, dist[node.end]));
				}
			}
		}
		
	}
}

시간 복잡도

o(n^2)