[알고리즘/자바] 다익스트라 알고리즘 (Dijkstra Algorithm)

이름만 들어도 어려울 것만 같은 다익스트라...

컴퓨터 과학자 에츠허르 데이크스트라 이름을 따서 만들었다고 한다.

(나도 내 이름을 딴 알고리즘 만들고 싶다...ㅎㅎ)

어쨌든 어렵다고 생각했던 다익스트라를 파헤쳐보자!~

레스 기릿

---

다익스트라 알고리즘이란?

-> 간단하게 하나의 정점에서 다른 점들로 가는 최단경로를 구하고 싶을 때 사용한다. (최단거리를 구하고 싶을 때 사용!)

 

시작점을 D로 잡고 나머지 점까지의 최단거리를 구해보자. D는 출발점이기 때문에 최단거리가 0이므로 0으로 초기화한다. 

D를 제외한 최적경로는 아직 연결이 안 돼있으므로 무한대로 초기화한다.

 

A	B	C	D	D
INF	INF	INF	0	INF

 

위에서 현재 최단거리가 가장 짧은 노드를 고른다. D번 노드이다. D번 노드에서 뻗어나가는 화살표를 살펴보면 C번 노드로 가는 것 하나뿐이다. 

C번 노드를 살펴보자. C번 노드의 현재 최단거리(INF)와, D번 노드의 최단거리(0) + D에서 C로 가는 경로(4) 값 중 더 작은 값으로 C번노드의 최단거리로 갱신한다. 

INF와 (0 + 4)를 비교해보면 (0 + 4)가 더 작은 값이므로 C의 현재 최단거리를 4로 갱신한다. 

 

A	B	C	D (checked)	E
INF	INF	4	0	INF

 

D에서 이어진 모든 점을 봤다면 D노드를 방문 처리해준다.(checked 표시)

 

A	B	C	D (checked)	E
INF	INF	4	0	INF

 

갱신된 최단거리는 위와 같다.

 

checked 표시가 된 노드를 제외하고 현재 최단거리가 가장 짧은 노드를 고른다. C번 노드이다. C번 노드에서 뻗어나가는 화살표들은 A방향(2) , E방향(6) 두 개다. 

먼저 A방향부터 계산하면 A번 노드의 현재 최단거리(INF)와, C번노드의 최단거리(4) + C에서 A로 가는 경로(2) 값 중 더 작은 값으로 A번노드의 최단거리로 갱신한다. 

INF와 6 중 6이 더 작은 값이므로 A의 현재 최단거리를 6으로 갱신한다.

 

A	B	C	D (checked)	E
6	INF	4	0	INF

 

다음으로 E방향(6)을 계산해보자. E번 노드의 현재 최단거리(INF)와, C번 노드의 최단거리(4) + C에서 E로 가는 경로(6) 값 중 더 작은 값으로 E번 노드의 최단거리로 갱신한다. 

INF와 6 중 6이 더 작은 값이므로 E의 현재 최단거리를 10으로 갱신한다.

 

A	B	C	D (checked)	E
6	INF	4	0	10

 

C에서 뻗어나가는 모든 노드를 확인했기 때문에 C를 방문 처리해준다.

 

A	B	C (checked)	D (checked)	E
6	INF	4	0	10

 

이런 식으로 계속해서 반복하다가 모든 점이 방문처리가 되면 시작점인 D노드를 기준으로 다른 점들까지의 최단거리를 구할 수 있게 된다.

 

위와 같은 메커니즘을 손으로 한번 해보고 이해를 하는 것을 추천한다!!

---

구현

위와 같은 방법으로 풀이를 하는 경우도 있고, 더 빠르게 구현할 수 있게 우선순위 큐를 이용하는 방법도 있다. 

 

1. 일반 배열을 이용한  풀이.

package graph;

import java.util.Arrays;
import java.util.Scanner;

public class Dijkstra {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int[][] adj = new int[V][V];
		for (int i = 0; i < E; i++) {
			adj[sc.nextInt()][sc.nextInt()] = sc.nextInt();
		}
		int[] D = new int[V];
		Arrays.fill(D, Integer.MAX_VALUE);
		boolean[] check = new boolean[V];

		D[0] = 0;
		for (int i = 0; i < V - 1; i++) {
			int min = Integer.MAX_VALUE;
			int index = -1;
			for (int j = 0; j < V; j++) {
				// 아직 처리하지 않았으면서, 가장 짧은 거리라면
				if (!check[j] && min > D[j]) {
					index = j;
					min = D[j];
				}
			}

			for (int j = 0; j < V; j++) {
				// 아직 처리하지 않았으면서 경로가 존재하고, index까지의 거리 + index부터 j까지의 거리가 D[j]보다 작다면
				if (!check[j] && adj[index][j] != 0 && D[index] != Integer.MAX_VALUE
						&& D[index] + adj[index][j] < D[j]) {
					D[j] = D[index] + adj[index][j];
				}
			}
			check[index] = true;
		}
		System.out.println(Arrays.toString(D));
	}

}

 

2. 우선순위 큐를 이용한 풀이 ( 시간 효율성이 훨씬 뛰어나서 공부해보기를 추천한다.)

package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Dijkstra_pq {
	
	static class Edge implements Comparable<Edge> {
		int v, weight;

		public Edge(int v, int weight) {
			this.v = v;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.weight, o.weight);
		}

		@Override
		public String toString() {
			return weight + "";
		}

	}



	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		List<Edge>[] adj = new ArrayList[V];
		for (int i = 0; i < V; i++)
			adj[i] = new ArrayList<>();
		for (int i = 0; i < E; i++) {
			// 첫번째가 출발지, 두번째가 도착지, 세번째가 가중치ㅋ
			adj[sc.nextInt()].add(new Edge(sc.nextInt(), sc.nextInt()));
		}
		//
		// dijkstra
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		boolean[] check = new boolean[V];
		Edge[] D = new Edge[V];
		// 0번에서 출발하는걸로.
		for (int i = 0; i < V; i++) {
			// 원하는 출발지
			if (i == 0) {
				D[i] = new Edge(i, 0);
			} else {
				D[i] = new Edge(i, Integer.MAX_VALUE);
			}
			pq.add(D[i]);
		}
		while (!pq.isEmpty()) {
			Edge edge = pq.poll();

			for (Edge next : adj[edge.v]) {
				// check되지 않았으면서, D[next.v]가 D[edge.v] + next.weight 보다 더 크다면 갱신
				if (!check[next.v] && D[next.v].weight > D[edge.v].weight + next.weight) {
					D[next.v].weight = D[edge.v].weight + next.weight;
					// decrease key
					pq.remove(D[next.v]);
					pq.add(D[next.v]);
				}
			}
			check[edge.v] = true;
		}
		System.out.println(Arrays.toString(D));
	}
}

---