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

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

그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다.

 

탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, 음의 가중치(음의 값)가 없어야한다.

음의 가중치가 존재하게 되면, 최소 비용의 음의 무한대값이 생성될 수 있으며 그리디 알고리즘을 적용할 수 없다.

 

인접 행렬로 표현된 그래프의 경우 O(n^2)의 복잡도를 가지며, 우선순위 큐를 사용하여 시간복잡도를 O(m logn)까지 낮출 수 있다.

 

 

매커니즘

(1) 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다 (그리디)
(2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 (DP)

 

 

예시

https://mag1c.tistory.com/451

[백준 1916번 / Java] 최소비용 구하기 / 다익스트라(Dijkstra) - DP

 

위 포스팅의 백준 1916번 문제를 예시로 들어 다익스트라 알고리즘을 구현해보자.

 

아래는 문제의 입력 예시 부분이며, 직접 그림으로 그려서 표현해보았다.

 

 

 또한 다익스트라 알고리즘 구현을 위해 필요한 우선순위 큐(선택)와 방문 체크 및 최단 경로를 기록할 수 있는 배열 두 개를 준비한다.

 

우선순위 큐에는, 정점과 출발지에서 정점까지 가는 최소거리를 저장한다.

또한 최단거리를 비교하여 입력할 수 있게, dist배열에는 최대로 들어갈 수 있는 길이의 값보다 큰 수를 입력하는 것이 좋다.

PriorityQueue = []
check = [F, F, F, F, F]
dist = [max, max, max, max, max]

 

구현할 때, 위에서 언급한 매커니즘대로 적용만 시키면 된다. 시작해보자

 

 

 

출발지인 1번 노드의 경우에서 보자. (참고 : 1번에서 1번까지의 길이는 출발지이기 때문에 0이다.)

출발지를 우선순위 큐에 입력한 후

PriorityQueue = [[1, 0]]
check = [T, F, F, F, F]
dist = [0, max, max, max, max]

 

방문한 노드에서 또 갈 수 있는 인접 노드들의 비용을 갱신하며, 방문하지 않은 노드의 경우 우선순위 큐에 갱신한다.

이 때, 우선순위 큐를 통해 비용이 가장 작은 순으로 먼저 입력될 것이다.

PriorityQueue = [[4, 1], [2,2], [3,3], [5,10]]
check = [T, F, F, F, F]
dist = [0, 2, 3, 1, 10]

 

방문하지 않은 노드 중에서 가장 비용이 작은 노드를 선택하여 또 방문한다.

여기서부터는 모든 노드를 탐색할 때 까지 무한반복이다.

방문 여부를 확인하고 나서 더 적은 비용을 갱신하고, 큐에 저장하고, 또 가장 작은노드를 먼저 탐색할 것이다.

이제 설명없이 쭉쭉 나열해보겠다.

PriorityQueue = [[2,2], [3,3], [5,10], [5,4]]
check = [T, F, F, T, F]
dist = [0, 2, 3, 1, 4]

PriorityQueue = [[3,3], [5,4], [5,10]]
check = [T, T, F, T, F]
dist = [0, 2, 3, 1, 4]

PriorityQueue = [[5,4], [5,10]]
check = [T, T, T, T, F]
dist = [0, 2, 3, 1, 4]

PriorityQueue = [[5,10]]
check = [T, T, T, T, T]
dist = [0, 2, 3, 1, 4]

PriorityQueue = []
check = [T, T, T, T, T]
dist = [0, 2, 3, 1, 4]

 

이렇게 방문이 끝나게되면, 결국 출발지점부터 도착지점까지의 최단경로가 dist[도착지점] 배열 안에 들어있을 것이다.

 

 

아래 주석을 잘 해놓은 예시 코드가 있어, 출처를 남기고 공유한다.

https://sskl660.tistory.com/59

[Java]다익스트라 알고리즘(Dijkstra Algorithm)

package Graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
sample input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
 */

public class Dijkstra2 {
	static int V, E, start;
	static ArrayList<ArrayList<Node>> graph;

	static class Node {// 다음 노드의 인덱스와, 그 노드로 가는데 필요한 비용을 담고 있다.
		int idx, cost;

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

	public static void main(String[] args) throws IOException {
		// 초기화
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(br.readLine());
		graph = new ArrayList<ArrayList<Node>>();
		for (int i = 0; i < V + 1; i++) {
			graph.add(new ArrayList<Node>());
		}
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			// 문제에서는 유향 그래프에서의 다익스트라 알고리즘(이 조건도 문제에 따라 중요하다!).
			graph.get(s).add(new Node(e, c));
		}

		// 다익스트라 알고리즘 초기화
		int[] dist = new int[V + 1]; // 최소 비용을 저장할 배열
		for (int i = 0; i < V + 1; i++) {
			dist[i] = Integer.MAX_VALUE;
		}

		// 주의점 1. 다익스트라 알고리즘의 최소비용을 기준으로 추출해야 한다. 최대 비용을 기준으로 하는 경우 최악의 경우 지수시간 만큼의 연산을
		// 해야한다!
		PriorityQueue<Node> q = new PriorityQueue<Node>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
		// 시작 노드에서, 시작 노드로 가는 값이 초기에 가장 짧은 비용을 갖는 노드이다.
		// 즉, 도착 정점은 start, 비용은 0인 노드를 가장 먼저 선택할 것이다.
		q.offer(new Node(start, 0));
		// 해당 노드를 선택한 것이나 마찬가지 이므로, dist[start] = 0으로 갱신.
		dist[start] = 0;
		while (!q.isEmpty()) {
			Node curNode = q.poll();

			// 목표 정점이 꺼내 졌다면, 해당 노드까지는 최솟값 갱신이 완료 되었다는 것이 확정이다(다익스트라 알고리즘).
			// 따라서, 반복문을 종료해도 되지만, 해당 코드는 시작 정점에 대하여 모든 정점으로의 최단 경로를 구하는 것을 가정한다.
			// 아래 주석된 코드는 목표 정점이 구해졌다면 빠르게 탈출할 수 있는 조건이다.
//			if (curNode.idx == end) {
//				System.out.println(dist[curNode.idx]);
//				return;
//			}

			// 꺼낸 노드 = 현재 최소 비용을 갖는 노드.
			// 즉, 해당 노드의 비용이 현재 dist배열에 기록된 내용보다 크다면 고려할 필요가 없으므로 스킵한다.
			// 주의점 2 : 중복노드 방지1 : 만일, 이 코드를 생략한다면, 언급한 내용대로 이미 방문한 정점을 '중복하여 방문'하게 된다.
			// 만일 그렇다면, 큐에 있는 모든 다음 노드에대하여 인접노드에 대한 탐색을 다시 진행하게 된다.
			// 그래프 입력이 만일 완전 그래프의 형태로 주어진다면, 이 조건을 생략한 것 만으로 시간 복잡도가 E^2에 수렴할 가능성이 생긴다.
			if (dist[curNode.idx] < curNode.cost) {
				continue;
			}

			// 선택된 노드의 모든 주변 노드를 고려한다.
			for (int i = 0; i < graph.get(curNode.idx).size(); i++) {
				Node nxtNode = graph.get(curNode.idx).get(i);
				// 만일, 주변 노드까지의 현재 dist값(비용)과 현재 선택된 노드로부터 주변 노드로 가는 비용을 비교하고, 더 작은 값을 선택한다.
				// 주의점 3 : 중복노드 방지 2 : 만일, 조건문 없이 조건문의 내용을 수행한다면 역시 중복 노드가 발생한다.
				// 간선에 연결된 노드를 모두 넣어준다면 앞서 언급한 정점의 시간 복잡도 VlogV를 보장할 수 없다.
				// 마찬가지로 E^2에 수렴할 가능성이 생긴다. 따라서 이 조건 안에서 로직을 진행해야만 한다.
				if (dist[nxtNode.idx] > curNode.cost + nxtNode.cost) {
					dist[nxtNode.idx] = curNode.cost + nxtNode.cost;
					// 갱신된 경우에만 큐에 넣는다.
					q.offer(new Node(nxtNode.idx, dist[nxtNode.idx]));
				}
			}
		}

		// 결과 출력
		System.out.println(Arrays.toString(dist));
	}
}

 

 

 

관련 문제풀이

https://mag1c.tistory.com/451

[백준 1916번 / Java] 최소비용 구하기 / 다익스트라(Dijkstra) - DP

https://mag1c.tistory.com/453