최단 경로 - 다익스트라 Dijkstra

백준 1916 골드5(자바)

최단 경로 구하는 알고리즘

1. 다익스트라
2. 벨만 포드
3. 플로이드 와샬

다익스트라 Dijkstra

: 그래프에서 노드에서 노드까지 최단경로를 구하는 알고리즘으로 시간복잡도는 O(E logV)이다.

에지가 모두 양수일때 사용
간선의 가중치가 같다면 DFS, BFS를 사용

구현

인접 리스트, 최단 경로 배열, 방문한 노드 확인하는 배열, 우선순위 큐 4개가 필요

1. 인접 리스트로 그래프 구현하기
2. 최단 경로 배열 초기화하기(0과 Max값으로)
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 우선순위 큐에 넣기
   (최소 비용을 갖는 노드를 선택하는 과정에서 우선순위 큐를 이용해야 시간복잡도가 좋게 나온다.)
4. 우선순위 큐에서 노드를 꺼낸 후 그 노드와 이웃한 노드를 이용해 최단 경로 배열 업데이트하기
5. 업데이트하는데 사용한 이웃 노드의 갱신된 값을 우선순위 큐에 넣기
6. 3, 4, 5를 반복해서 최단 경로 배열을 완성

bfs와 구현상 차이

(bfs와 달리 가중치가 있는 그래프에서 사용 가능)
1. PriorityQueue를 이용
2. 해당 노드까지 오는데 최소 가중치를 저장하는 최단경로 배열
3. node 클래스를 구현하고 implements Comparable을 추가해 compareTo 함수를 구현해서 1번이 가능하도록

직접 해보기

s : 1

	1	2	3	4	5
1	0	2	3	inf	1
2		0	4	5	inf
3			0	6	inf
4				0	inf
5					0

가장 비용이 작은 5번 노드 거쳐가는 경우 고려

1 → 5(1) →

	1	2	3	4	5
1	0	2	3	inf	1
2		0	4	5	inf
3			0	6	inf
4				0	inf
5					0

2번 노드 거쳐가는 경우 고려

1 → 2(2) →

	1	2	3	4	5
1	0	2	3	7	1
2		0	4	5	inf
3			0	6	inf
4				0	inf
5					0

3번 노드 거쳐가는 경우 고려

1 → 3(3) → 4

	1	2	3	4	5
1	0	2	3	7	1
2		0	4	5	inf
3			0	6	inf
4				0	inf
5					0

백준 1916

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int V = sc.nextInt();
		int E = sc.nextInt();

		// 인접 리스트
		ArrayList<ArrayList<Node>> graph = new ArrayList<>();

		// 초기화
		for (int i = 0; i < V + 1; i++) {
			graph.add(new ArrayList<>());
		}

		int x, y, w;
		for (int i = 0; i < E; i++) {
			x = sc.nextInt();
			y = sc.nextInt();
			w = sc.nextInt();
			// 단방향
			graph.get(x).add(new Node(y, w));
		}

		int start = sc.nextInt();
		int end = sc.nextInt();

		// 최단 경로 배열
		int[] dist = new int[V + 1];

		//System.out.println(Integer.MAX_VALUE);
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;

		// 방문한 노드 배열
		boolean[] visited = new boolean[V + 1];

		// 우선순위 큐
		PriorityQueue<Node> pq = new PriorityQueue<>();
		
		pq.offer(new Node(start, 0));

		while (!pq.isEmpty()) {
			int nowNode = pq.poll().n;

			if (visited[nowNode]) {
				continue;
			}
			visited[nowNode] = true;

			// now 노드와 연결된 노드 비교
			for (Node next : graph.get(nowNode)) {
				// 연결된 노드 next가 now 노드를 거치면 더 비용이 작아지는지 확인
				
				if (dist[next.n] > dist[nowNode] + next.w) {
					dist[next.n] = dist[nowNode] + next.w;

					// 우선순위 큐에 넣기
					pq.offer(new Node(next.n, dist[next.n]));
				}
			}
		}

		System.out.println(dist[end]);
		sc.close();

	}
	
	static class Node implements Comparable<Node> {
		int n, w;

		public Node(int n, int w) {
			this.n = n;
			this.w = w;
		}

		// 비교할 때 weight 기준으로
		@Override
		public int compareTo(Node node) {
			return Integer.compare(this.w, node.w);
		}

	}

}