[알고리즘] 다익스트라 알고리즘

1. 다익스트라 알고리즘

가중치가 있는 그래프에서 출발점 ~ 목표점까지의 최단거리를 구할 때 사용하는 알고리즘

2. 다익스트라 알고리즘 구현 준비

• 가중치간 최단 거리를 저장하기 위한 dist[N+1] 배열을 생성
  => 최단 경로를 만날 때 마다 비교해서 저장 (이 때, Integer.MAX_VALUE로 초기화)
• PriorityQueue에 연결된 간선을 add
  => 가중치가 낮은 경로부터 탐색하기 위함
• ArrayList<ArrayList>
  => 1~N 간선까지 서로 연결된 정보를 저장하기 위함
• to(연결된 노드), weight(가중치) 두 정보를 갖는 클래스 생성

3. 동작 과정

• 시작점을 Queue에 삽입
• 큐가 빌 때까지 while문을 돌면서 연결된 노드들과의 경로를 탐색
• 이 때, 기존에 저장해놓은 경로가 현재 방문한 결과보다 크다면 현재 결과를 dist에 저장

4. 예시 문제

• 프로그래머스 배달 문제

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class 배달 {
	
	static class Point implements Comparable<Point> {
		int to, weight;
		
		Point(int to, int weight) {
			this.to = to;
			this.weight = weight;
		}
		
		@Override
		public int compareTo(Point o) {
			return this.weight - o.weight;
		}
		
	}
	
	public static void main(String[] args) {
		int N = 5;
		int[][] road = {{1,2,1},{2,3,3},{5,2,2},{1,4,2},{5,3,1},{5,4,2}};
		int K = 3;
		
		ArrayList<ArrayList<Point>> adj = new ArrayList<ArrayList<Point>>();
		PriorityQueue<Point> pq = new PriorityQueue<Point>();
		int[] arr = new int[N+1];
		
		Arrays.fill(arr, Integer.MAX_VALUE);
		for(int i=0; i<=N; ++i) adj.add(new ArrayList<Point>());
		
		for(int i=0; i<road.length; i++) {
			int x = road[i][0];
			int y = road[i][1];
			int z = road[i][2];

			adj.get(x).add(new Point(y, z));
			adj.get(y).add(new Point(x, z));
		}
		
		arr[1] = 0;
		pq.offer(new Point(1, 0));
		
		while(!pq.isEmpty()) {
			Point cur = pq.poll();
			
			for(Point p : adj.get(cur.to)) {
				if(arr[p.to] > arr[cur.to] + p.weight) {
					arr[p.to] = arr[cur.to] + p.weight;
					pq.offer(p);
				}
			}
		}
		
		int count = 0;
		for(int i=0; i<arr.length; i++) {
			if(arr[i] <= K) {
				count ++;
			}
		}
		
		System.out.println(count);
	}

}