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

공부가 목적인 포스팅으로, 미흡한 점이 있다면 피드백 부탁드리겠습니다.

 

 다익스트라로 불리는 이 알고리즘은 그래프의 가중치를 활용하여 최단 경로를 구하는 알고리즘입니다. 

이 알고리즘은 어떤 한 정점(노드)에서 나머지 모든 정점(노드)에 대하여 최단 거리를 알려줍니다. 하지만 이때 단 하나의 음의 간선(음의 가중치)이 존재하면 안됩니다. 말 그대로 '최단 거리'를 구하고자 하는 것이기 때문에 음의 간선이 존재하면 최단 거리의 의미가 퇴색됩니다.  

 

 다익스트라 알고리즘은 그리디 알고리즘 + 다이나믹 프로그래밍(DP) 알고리즘을 합친 버전이라 볼 수 있습니다.  

방문하지 않은 정점 중 가장 가중치가 적은 정점을 선택하는 방법(그리디) + 하나의 최단 거리를 구할 때 그 이전에 구한 최단 거리 정보를 이용하는 방법(DP)

 

 저는 이 글에서 인접리스트와 우선순위 큐(힙)를 이용하여 구현하는 방법을 설명하겠습니다. 이 방법이 효율적이고 기존 모든 배열을 탐색하는 방법에서 개선된 방법이기도 합니다. 

 

먼저 코드를 보여드리자면, 

 

백준 / 1753번 / 최단 경로

public class BOJ_1753 {
	// BOJ / 1753번 / 최단 경로 / 다익스트라  / 골드5 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		int v = Integer.parseInt(stk.nextToken()); // 정점 갯수
		int e = Integer.parseInt(stk.nextToken()); // 간선 갯수	
		int k = Integer.parseInt(br.readLine()); // 시작 번호
		
        	// 모든 정점에 대해 인접 리스트를 만든다.
		ArrayList<Edge> graph[] = new ArrayList[v];
		// 초기화.
		for(int i=0; i<v; i++) {
			graph[i] = new ArrayList<>();
		}
        	// 입력 받음
		for(int i=0; i<e; i++) {
			stk = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(stk.nextToken()); // a -> b = c
			int b = Integer.parseInt(stk.nextToken());
			int c = Integer.parseInt(stk.nextToken());
			graph[a-1].add(new Edge(b-1,c));
		}
		// 최단 경로를 저장할 배열 
		int dist[] = new int[v];
        	// 배열 값을 최댓값으로 초기화 시켜준다.
		Arrays.fill(dist, Integer.MAX_VALUE);
        	// 출발점에 대한 최단 경로는 0이다.
		dist[k-1] = 0;
		
        	// 우선순위 큐를 이용하여 최단 경로를 갱신한다.
		PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.w - o2.w;
			}
		});
        	// 시작점을 큐에 넣어준다.
		pq.add(new Edge(k-1, 0));
		// 갱신 로직
		while(!pq.isEmpty()) {
			Edge now = pq.poll();
            		// 기존에 갱신된 값보다 현재 값이 더 크면 검사하지 않는다.
			if(now.w > dist[now.v]) continue;
			for(int i=0; i<graph[now.v].size(); i++) {
				Edge next = graph[now.v].get(i);
                		// 다음 정점의 최단 경로 > 현재 정점 까지 최단 경로 + 
                        	// 현재 정점에서 이어진 다음 정점까지의 경로
				if(dist[next.v] > dist[now.v] + next.w) {
					dist[next.v] = dist[now.v] + next.w;
					pq.add(new Edge(next.v, dist[next.v]));
				}
			}
		}
		
		StringBuffer sb = new StringBuffer();
		
		for(int i = 0; i<dist.length; i++) {
			if(dist[i] == Integer.MAX_VALUE) sb.append("INF").append("\n");
			else sb.append(dist[i]).append("\n");
		}
		System.out.println(sb);
	}
}

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

 ArrayList와 우선순위 큐 자료구조를 이용했습니다. 여기서 중요한 것은 최단 경로를 저장할 dist배열입니다. 출발할 시작점은 자기 자신과의 거리이므로 0입니다. 하지만 나머지 정점은 INF값으로 초기화시켜줍니다. 위 풀이에서는 Integer.MAX_VALUE로 초기화 했지만 상황에 따라 오버플로우가 발생할 수 있습니다. 

 

 INF는 간선 가중치의 최댓값 * 정점 갯수 -1 보다 큰 값을 사용해야 합니다. 기준이 되는 시작점에서 도착점까지 모든 정점을 지나고 모든 간선들이 동일한 값을 지니고 있는 최악의 경우를 생각해줘야 하기 때문입니다. 무작정 Integer.MAX_VALUE 값을 넣어다가는 오버플로우가 발생할 수 있습니다. 그래서 최댓값은 적당한 값으로 설정하는 것이 좋습니다. 

 

 기본적으로 다익스트라 알고리즘의 핵심은 최소 비용을 갖는 정점(출발점)을 선택 후, 가까운 주변 정점의 최단 경로를 갱신해주는 것입니다. 이를 위의 코드에 대입해보면, 시작점은 항상 0의 최소 비용을 갖으므로 우선순위 큐에 먼저 삽입해줍니다. 그리고 삽입한 정점(시작점)을 추출하고, 이 정점을 기준으로 연결된 다른 정점의 최단 경로를 조건문을 통하여 갱신시켜줍니다. 그리고 갱신된 정점을 다시 우선순위 큐에 삽입해주는 것입니다. 

 

 연결되지 않은 정점은 신경쓰지 않아도 됩니다. 즉, 최소 비용을 갖는 정점의 주변 노드만 선택해주는 것이 우선순위 큐를 이용하는 핵심입니다. 연결되지 않은 정점(시작점에서 갈 수 없는 정점)은 그대로 초기화된 INF값을 갖게 될 것이고 우리는 이 값을 통하여 연결되지 않았다는 사실을 알 수 있습니다. 

 

 그렇다면, 우선 순위 큐에 대해 필요한 연산은 추출과 삽입입니다. 이 연산의 합이 시간 복잡도가 될 것입니다. 우선순위 큐에 들어가는 정점의 수는 갱신이 필요한 주변 정점의 수입니다. 이것은 갱신이 필요한 간선의 수로 바꿔 말할 수 있습니다. 즉, 우선 순위 큐에 삽입하는 최대 횟수는 간선의 개수입니다. 모든 간선에 대해서 삽입 연산이 발생한다면 최대 O(ElogE)의 시간이 걸릴 것이고 , 간선의 최대 개수는 모든 정점들이 서로 연결될 경우보다 작거나 같을 것이므로(E <= V^2), 최대 O(ElogV)의 시간이 걸린다고 바꿔 말할 수 있습니다. 

 

 위에서는 각 정점을 삽입하는 연산을 설명하였으니, 이제는 우선순위 큐에서 추출하는 연산을 해야합니다. 각 정점들을 우선 순위 큐에서 추출하는 연산은 시작점에서 출발하여 다른 모든 정점까지 갈 수 있다는 가정하에, 최대 V개의 정점을 우선 순위 큐에서 추출할 것입니다. 여기서 이미 방문했던 정점에 대하여 방문 체크, 혹은 기존에 갱신한 값보다 더 큰 값을 가중치로 가질 경우 연산을 하지 않는 중복 연산을 방지했다는 가정하에 최대 V개인 것입니다. V개 정점에 대하여 추출을 해야 하므로 최대 O(VlogV)의 시간이 걸릴 것입니다. 

 

 위의 삽입과 추출 두 연산을 해줘야 하므로 총 시간 복잡도는 O(ElogV) + O(VlogV) = O((V+E) logV)를 갖게 됩니다. 

 

 설명이 부실했지만, 우선순위 큐를 이용할 때는 꼭 방문 체크 혹은 중복 갱신을 방지해줘야 합니다. 그렇지 않다면 무차별적으로 우선순위큐에 넣게 되어 모든 정점을 재방문하여 연산을 하게 됩니다. 그래서 방문 체크 배열을 만들거나 위의 코드처럼 특정 정점이 기존의 갱신한 값보다 더 큰 값을 가중치로 갖는 경우 중복 갱신을 방지하는 따로 코드를 작성하여야 합니다. 

 

 추가적으로 설명하자면, 만약 두 정점에 대해서 연결된 간선이 1개 이상일 경우, 이 간선들을 모두 판별하는 것이 아니라 우선순위 큐 코드쪽에 있는 Comparator 인터페이스를 통해 가중치를 기준으로 오름차순 정렬하여 큐에 삽입합니다.(다른 방법도 가능합니다.) 그렇다면 특정 정점에 대해서 연결되어 있는 간선 중에 최소 비용을 갖는 간선이 가장 먼저 큐에서 추출될 것이고 이를 활용하여 방문 체크 혹은 가중치 값 계산을 통하여 다음 간선들에 대한 중복 연산을 막는 것입니다. 

 

  *참고 

우선 순위 큐에 삽입 추출 연산은 O(logN)입니다.