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

다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.

알고리즘의 핵심 원리는 그리디이다.

매 단계에서 가장 비용이 적게 드는 노드를 선택하고, 그 노드를 거쳐가는 경로를 확인하며 거리를 갱신한다.

1. 현재까지 알려진 거리 중 가장 짧은 곳을 먼저 방문(우선 순위 큐 활용).
2. 선택한 노드를 거쳐서 인접 노드로 가는 거리가 기존에 알고 있던 거리보다 짧으면 갱신.

가중치가 음수일 때 불가능한 이유

다익스트라의 대전제인 "지금 꺼낸 최단 거리가 앞으로도 최단 거리일 것이다"라는 그리디 속성이 깨지기 때문이다.

가중치에 음수가 있다면 벨만-포드(Bellman-Ford) 알고리즘을 사용하면 된다.

시간복잡도

우선순위 큐 사용 시 모든 간선을 한 번씩 확인($E$)하며, 각 간선에 대해 힙에 넣고 빼는 연산($logE$) 수행.

따라서 기본적으로 $O(ElogE)$이며, 보통 $E \le V^2$이므로 $O(ElogV)$라고 표현.

문제

백준 1504번 특정한 최단 경로

풀이

import java.util.*;

class Edge implements Comparable<Edge>{
	int ver;
	int cost;
	
	public Edge(int ver, int cost) {
		this.ver = ver;
		this.cost = cost;
	}
	
	//우선순위 큐를 사용하기 위한 정렬 규칙
	@Override
	public int compareTo(Edge e) {
		return this.cost - e.cost;
	}
}

public class Main{
	static List<List<Edge>> graph = new ArrayList<>();
	static int n;
	
	public static int[] Dijk(int ver, int cost) {
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		int[] dis = new int[n+1];; //출발 노드에서 v까지 가는 현재까지 알려진 최소 비용
		Arrays.fill(dis, Integer.MAX_VALUE); //최소 비교 갱신을 위해
		dis[ver] = 0;
		pq.offer(new Edge(ver, cost));
		
		while(!pq.isEmpty()) {
			// 현재까지 가장 비용이 작은 경로 하나 꺼냄
			Edge cur = pq.poll();
			
			// 이미 이 정점에 더 짧은 경로로 온 적 있으면 버림
            // 이거 없으면 쓸 때 없이 또 주변 다 탐색함
			if (dis[cur.ver] < cur.cost) continue;
			
			// 현재 정점에서 갈 수 있는 모든 다음 정점 탐색
			for(Edge e : graph.get(cur.ver)) {
				if(dis[e.ver] > cur.cost + e.cost) {
					//현재 경로를 거쳐서 다음 경로로 가는 비용이 더 작다면 갱신
					dis[e.ver] = cur.cost + e.cost;
					pq.offer(new Edge(e.ver , cur.cost + e.cost));
				}
			}
		}
		
		return dis;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int e = sc.nextInt();

		for(int i=0; i<=n; i++) {
			graph.add(new ArrayList<>());
		}
		for(int i=0; i<e; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			graph.get(a).add(new Edge(b, c));
			graph.get(b).add(new Edge(a, c));
		}
		
		int v1 = sc.nextInt();
		int v2 = sc.nextInt();
		
		//1번부터 시작했을 때
		//v1부터 시작했을 때
		//v2부터 시작했을 때
		//각각(dis배열 함수안에서 새로 만들어서 반환!) 구해서 연결시키면 됨
		int[] dis1 = Dijk(1,0);
		int[] disV1 = Dijk(v1, 0);
		int[] disV2 = Dijk(v2, 0);
		
		//1 -> v1 -> v2 -> n, 1-> v2 -> v1 -> n 비교 (오버플로우 방지를 위한 long)
		long answer = (long)Math.min((long)dis1[v1] + disV1[v2] + disV2[n], (long)dis1[v2] + disV2[v1] + disV1[n]);
		
		//마지막이 INF보다 클 경우 도달하지 못한다는 뜻
		if(answer >= Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(answer);
	}
}