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

1. 기본 개념 🍄

1. 최단 경로

  가중치 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소가 되는 경로

2. 대표적인 최단 경로 알고리즘

	다익스트라(Dijkstra)	벨만포드(Bellman-Ford)	플로이드 와샬(Floyd-Warshall)
정의	출발 정점로부터 모든 정점까지의 최단 경로를 구하는 알고리즘	출발 정점로부터 모든 정점까지의 최단 경로를 구하는 알고리즘	모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
특징	음의 가중치를 허용 X	음의 가중치를 허용 O	음의 가중치를 허용 O
사용하는 알고리즘	그리디 알고리즘	그리디 알고리즘	DP 알고리즘
시간복잡도	O(V ^ 2) 또는 O(E log V)	O(V ^ 2) 또는 O(E log V)	O(V ^ 3)

 

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

1. 개념

  출발 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘

(만약 모든 정점까지의 거리가 아닌 특정 정점까지의 거리를 알고 싶다면 해당 정점을 방문했을 때 빠져나오는 것을 고려할 수 있음 - 그리디 방식으로 동작하는 것에 기반한 구현)

2. 동작 방식

[한 줄 정리]

  아직까지 선택되지 않은 정점들 중에서, 시작점으로부터 최단거리가 가장 짧은 것을 방문하는 것!

[구체적 방식]

1. 출발 정점을 선택한다.
2. 최단 거리 테이블을 초기화한다. 
   최단 거리를 알 수 없는 경우 무한대로 지정
3. 방문하지 않은 정점들 중에서 최단 거리가 가장 짧은 정점에 방문한다.
4. 해당 정점으로부터 다른 정점으로 갈 수 있는 거리를 이용하여 최단 거리 테이블을 업데이트한다.
   더 짧은 거리를 만들 수 있는 경우에만 업데이트함.
5. 3번과 4번을 반복한다.

3. PRIM 알고리즘과 차이점

  PRIM 알고리즘과 다익스트라(Dijkstra) 알고리즘의 가장 큰 차이점은 '다음에 방문할 정점을 선택하는 방식'이다.

• PRIM 알고리즘
  이전에 방문한 정점에서부터 가장 짧은 거리의 정점을 방문함
• 다익스트라(Dijkstra) 알고리즘
  시작점으로부터 아직 방문한 지 않은 정점들 중 최단거리에 해당하는 정점을 방문함.

 

3. 예시를 통한 동작이해 🍆

  위와 같은 그래프가 있다고 하자.

  우선, 출발 정점을 선택한다. 여기서는 1번을 출발 정점이라고 하자.

  그리고 최단 거리 테이블을 초기화시키자. 출발 정점의 최단 거리는 당연히 0이다.

정점 번호	1	2	3	4	5	6
최단 거리	0	∞	∞	∞	∞	∞

---

정점 번호	1	2	3	4	5	6
최단 거리	0	∞	∞	∞	∞	∞

  방문하지 않은 정점들 중에서 최단 거리가 가장 짧은 정점인 1번에 방문한다. (출발 정점을 처음부터 방문한 것으로 표현할 수도 있지만, 코드를 더 간단하게 만들기 위하여 해당 방식을 사용한다.)

정점 번호	1	2	3	4	5	6
최단 거리	방문	7	9	∞	∞	14

  그리고 해당 정점(1번 정점)으로부터 다른 정점으로 갈 수 있는 거리를 이용하여 최단 거리 테이블을 업데이트한다.

---

정점 번호	1	2	3	4	5	6
최단 거리	방문	7	9	∞	∞	14

  방문한 1번 정점을 제외하고 방문하지 않은 정점들 중 최단 거리가 가장 짧은 정점인 2번을 방문한다.

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	9	22	∞	14

  그리고 해당 정점(2번 정점)으로부터 다른 정점으로 갈 수 있는 거리를 이용하여 최단 거리 테이블을 업데이트한다. 이때, 출발 정점으로 부터 3번 정점으로 갈 수 있는 새로운 거리인 17을 알더라도 최단 거리 테이블에 있는 3번 정점의 최단 거리 값이 더 작으므로 업데이트하지 않는다.

  이후의 동작 방식은 그림과 표만 있어도 충분히 이해할 수 있을 거라고 생각한다.

---

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	9	22	∞	14

[최단 거리 테이블 업데이트]

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	방문	20	∞	11

---

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	방문	20	∞	11

[최단 거리 테이블 업데이트]

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	방문	20	20	방문

---

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	방문	20	20	방문

(4번과 5번 중 어느 정점을 먼저 방문해도 상관없다.)

[최단 거리 테이블 업데이트]

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	방문	방문	20	방문

---

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	방문	방문	20	방문

[최단 거리 테이블 업데이트]

정점 번호	1	2	3	4	5	6
최단 거리	방문	방문	방문	방문	방문	방문

  이러한 절차를 거쳐서 모든 정점을 방문하게 된다. 실제 코드를 이용한 구현에서는 방문한 정점이더라도 최단 거리가 '방문'이라고 표시되지 않고 '최단 거리'를 표시하게 된다. 위에서는 이해를 돕기 위해 '방문'이라는 단어를 사용하였다.

  최종적으로 출발 정점(1번 정점)에서부터 모든 정점까지의 최단 거리는 아래와 같다.

정점 번호	1	2	3	4	5	6
최단 거리	0	7	9	20	20	11

  

4. 구현(JAVA) 🥜

  구현 방법에는 '순차 탐색'과 '우선순위 큐를 이용하는 방식'이 있다. 시간 복잡도에 관한 결론부터 얘기하자면 아래의 표와 같다.

구현 방식	순차 탐색	우선순위 큐를 이용하는 방식
시간 복잡도	O(V ^ 2)	O(E log V)

1. 순차 탐색

  순차 탐색은 2차원 배열을 이용하여 구현하였다. 현재 정점과 연결된 정점들을 일일이 확인해야 하므로 시간 복잡도는 O(V ^ 2)이다.

  입력은 정점 개수(N)와 출발 정점의 인덱스 번호(S)를 먼저 받는다. (위에서는 출발 정점의 번호를 이용하였는데 코드에서는 인덱스를 활용한다.) 그리고 N * N 행렬의 모습으로 가중치들을 받아온다.

6 0
0 7 9 0 0 14
0 0 10 15 0 0
0 0 0 11 0 2
0 0 0 0 6 0
0 0 0 0 0 0
0 0 0 0 9 0

public final class Main {
	
	static int V, S;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		// 정점 개수
		V = Integer.parseInt(st.nextToken());
		// 출발 정점 선택 - 동작방식(1) 
		S = Integer.parseInt(st.nextToken());
		
		// 가중치를 저장하는 2차원 배열
		int[][] weights = new int[V][V];
		for(int i = 0; i < V; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for(int j = 0; j < V; j++) {
				weights[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		boolean[] visited = new boolean[V];
		
		// 최단 거리 테이블 초기화 - 동작방식(2)
		int[] minDistances = new int[V];
		final int INF = Integer.MAX_VALUE;
		Arrays.fill(minDistances, INF);
		minDistances[S] = 0;
		
		int minDistanceToCurrentV, currentV;
		
		for(int vCnt = 0; vCnt < V; vCnt++) {
			
			// 방문할 정점
			currentV = -1;
			// 해당 정점까지의 최단 거리
			minDistanceToCurrentV = INF;
			
			// 방문 하지 않은 정점들 중에서
			// 최단 거리가 가장 짧은 정점에 방문 - 동작 방식(3)
			for(int i = 0; i < V; i++) {
				if(visited[i])
					continue;
				
				if(minDistances[i] < minDistanceToCurrentV) {
					minDistanceToCurrentV = minDistances[i];
					currentV = i;
				}
			}
			
			// 더 이상 방문 할 수 없는 경우
			if(currentV == -1) {
				break;
			}
			
			visited[currentV] = true;
			
			// 최단 거리 테이블 업데이트 - 동작 방식(4)
			for(int i = 0; i < V; i++) {
				if(visited[i])
					continue;
				
				if(weights[currentV][i] == 0)
					continue;
				
				if(minDistances[currentV] + weights[currentV][i] 
						< minDistances[i]) {
					minDistances[i] = minDistances[currentV] + weights[currentV][i];
				}
			}
		}
		
		System.out.println("출발 정점 : " + S);
		for(int i = 0; i < V; i++) {
			System.out.println("최단 거리[" + i + "] : " + minDistances[i]);
		}		
	}
}

2. 우선순위 큐(PQ)를 이용하는 방식

  PQ를 이용하여 각 간선들을 삽입 또는 삭제한다. 최대 E개를 삽입 또는 삭제할 수 있으므로 O(E log E)의 시간이 걸린다. (E개 * PQ에서 삽입 삭제 시간 logE)

  대게 그래프의 경우 V^2 > E 이므로 O(log E) = O(log V)로 표현할 수 있다. 그러므로 PQ를 이용한 시간복잡도는 O(E log V)가 된다. (참조)

public class Main {

	static int V, S;
	
	static class Vertex implements Comparable<Vertex> {
		public int idx;
		public int minDistance;
		
		public Vertex(int num, int minDistance) {
			this.idx = num;
			this.minDistance = minDistance;
		}

		@Override
		public int compareTo(Vertex o) {
			return this.minDistance - o.minDistance;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		// 정점 개수
		V = Integer.parseInt(st.nextToken());
		// 출발 정점 선택 - 동작방식(1) 
		S = Integer.parseInt(st.nextToken());

		// 가중치를 저장하는 2차원 배열
		int[][] weights = new int[V][V];
		for(int i = 0; i < V; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for(int j = 0; j < V; j++) {
				weights[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		boolean[] visited = new boolean[V];

		// 최단 거리 테이블 초기화 - 동작방식(2)
		int[] minDistances = new int[V];
		final int INF = Integer.MAX_VALUE;
		Arrays.fill(minDistances, INF);
		minDistances[S] = 0;
		
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		pq.offer(new Vertex(S, minDistances[S]));
		
		while(!pq.isEmpty()) {
			
			// 방문 하지 않은 정점들 중에서
			// 최단 거리가 가장 짧은 정점에 방문 - 동작 방식(3)
			Vertex currentV = pq.poll();
			int currentVIdx = currentV.idx;
			if(visited[currentVIdx]) {
				continue;
			}
			
			visited[currentVIdx]= true;
			
			// 최단 거리 테이블 업데이트 - 동작 방식(4)
			// 계속 탐색을 하기 위해 새로운 최단 거리가 만들어지면 PQ에 넣어주기 
			for(int i = 0; i < V; i++) {
				if(visited[i])
					continue;

				if(weights[currentVIdx][i] == 0)
					continue;

				if(minDistances[currentVIdx] + weights[currentVIdx][i] 
						< minDistances[i]) {
					minDistances[i] = minDistances[currentVIdx] + weights[currentVIdx][i];
					pq.offer(new Vertex(i, minDistances[i]));
				}
			}
		}

		System.out.println("출발 정점 : " + S);
		for(int i = 0; i < V; i++) {
			System.out.println("최단 거리[" + i + "] : " + minDistances[i]);
		}		
	}
}