[알고리즘] 다익스트라

Dijkstra 최단 경로 알고리즘

• 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는알고리즘
• 시간복잡도 : O(E logN) (N : 노드 수, E : 간선 수)
• 간선의 가중치가 양수인 경우만 가능 (음수인 경우 플로이드워셜 알고리즘 사용)
• 그리디 알고리즘 사용
• 우선순위 큐(힙 자료구조) 사용

  동작과BR

  1. 출발 노드를 설정
  2. 최단 거리 테이블 초기화
  3. 방문하지 않은 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 갱신
  5. 3, 4번 반복

구현

1. 출발 지점의 노드가 1이므로 우선순위 큐에 넣기, 출발 노드에서 출발 노드로의 거리는 0이므로 0으로 초기화

   노드 번호	1	2	3	4	5
   가중치	0	MAXVALUE	MAXVALUE	MAXVALUE	MAXVALUE

   우선순위 큐 : (거리: 0, 노드: 1)

2. 큐에서 노드 꺼내기 -> 해당 노드를 이미 처리했으면 무시하고 처리하지 않은 노드는 최소 비용 계산 => 2번(0 + 2), 3번(0 + 3)

   꺼낸 원소 : (거리: 0, 노드: 1)

   노드 번호	1	2	3	4	5
   가중치	0	2	3	MAXVALUE	MAXVALUE

   우선순위 큐 : (거리: 2, 노드: 2), (거리: 3, 노드: 3)

3. 과정 반복 => 3번(2 + 4)은 기존 거리 3보다 크므로 넘어감, 4번(2 + 5)
   꺼낸 원소 : (거리: 2, 노드: 2)

   노드 번호	1	2	3	4	5
   가중치	0	2	3	7	MAXVALUE

   우선순위 큐 : (거리: 3, 노드: 3), (거리: 7, 노드: 4)

4. 4번(3 + 6)으로 기존 거리 7보다 커서 넘어감
   꺼낸 원소 : (거리: 3, 노드: 3)

   노드 번호	1	2	3	4	5
   가중치	0	2	3	7	MAXVALUE

   우선순위 큐 : (거리: 7, 노드: 4)

5. 해당 노드에서 가는 길이 없어서 큐가 비어서 종료
   꺼낸 원소 : (거리: 7, 노드: 4)

   노드 번호	1	2	3	4	5
   가중치	0	2	3	7	MAXVALUE

   우선순위 큐 :

⭐ 관련 문제

백준 1753번 최단경로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static class Node{
		int v; // 간선
		int cost; // 가중치

		public Node(int v, int cost){
			this.v = v;
			this.cost = cost;
		}
	}

	static ArrayList<Node>[] graph; // 노드 정보 담는 리스트
	static boolean[] visited; // 방문 처리
	static int[] dist; // 최단 거리 테이블

	public static void main(String[] args) throws 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 s = Integer.parseInt(br.readLine());

		graph = new ArrayList[v + 1];
		visited = new boolean[v + 1];
		dist = new int[v + 1];

		// 그래프와 최단 거리 테이블 초기화
		for(int i = 1; i<=v; i++){
			graph[i] = new ArrayList<>();
			dist[i] = Integer.MAX_VALUE;
		}

		for(int i = 0; i<e; i++){
			// u -> v로 가는 가중치 w
			st = new StringTokenizer(br.readLine());
			int U = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			int W = Integer.parseInt(st.nextToken());

			graph[U].add(new Node(V, W));
		}

		// 다익스트라 수행
		dijkstra(s);
		for(int i = 1; i<=v; i++){
			System.out.println((dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]));
		}

	}

	static void dijkstra(int start){
		// 우선순위 큐 사용 - 가중치 기준으로 오름차순
		PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.cost - b.cost);
		queue.add(new Node(start, 0));
		dist[start] = 0;

		while(!queue.isEmpty()){
			// 최단 거리가 짧은 노드 꺼내기
			Node curr = queue.poll();
			int currV = curr.v;

			// 이미 방문한 노드는 무시
			if (!visited[currV]) {
				visited[currV] = true;

				for(Node n : graph[currV]){
					int v = n.v;
					int cost = n.cost;

					// 현재 노드 거리 + 확인하는 노드 거리가 최단 거리일 경우 업데이트
					if (!visited[v] && dist[currV] + cost < dist[v]){
						dist[v] = dist[currV] + cost;
						queue.add(new Node(v, dist[v]));
					}
				}
			}
		}
	}
}

백준 1504번 특정한 최단 경로