[Java] 다익스트라(Dijkstra, 데이크스트라) 알고리즘

다익스트라 알고리즘은 아래의 상황에서 사용합니다.

1. 음수 가중치가 존재하지 않는 방향성 그래프이며

2. 시작점이 주어지고 다른 모든 노드까지의 거리를 구하는 경우에

이 알고리즘의 시간복잡도는 노드의 수를 V, 간선의 수를 E 이라고 가정할 때 O((V + E)logV) 입니다. 그렇기 때문에 특히 노드의 수 제곱에 비해 간선의 수가 적은 희소그래프에서 주로 사용되며, cost 가 가장 작은 노드 선택을 위해 정점들을 Heap 형태로 저장합니다.

아래는 해당 다익스트라 알고리즘을 Java 로 구현한 내용입니다.

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Dijkstra {
	
	static int M = 100;		// 최대 노드의 수
	static int N = 100;		// 최대 간선의 수
	final static int INF = Integer.MAX_VALUE;
	
	static ArrayList adjList[] = new ArrayList[M + 1];
	static int visited[] = new int[M + 1];
	
	// 목적지가 없을 경우, 전 start 노드로부터 전 노드에 대한 최단 경로 탐색
	static void dijkstra(int start) {
		dijkstra(start, -1);
	}
	
	static void dijkstra(int start, int dest) {
		PriorityQueue pq = new PriorityQueue<>(M, new Comparator() {
			// 현재까지 구해진 노드까지의 합들 중 가장 작은 값을 선택
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
		});
		
		// 릴리즈 값(각 노드까지의 최단 거리) 초기화
		for(int i = 0; i <= M; i++) {
			visited[i] = INF;
		}
		visited[start] = 0;
		
		pq.add(new int[] { start, 0 });
		while(!pq.isEmpty()) {
			int curr[] = pq.poll();
			
			if (curr[0] == dest) {
				break;
			}
			
			for (int i = 1; i <= adjList[curr[0]].size(); i++) {
				int next[] = adjList[curr[0]].get(i).clone();
				next[1] += curr[1];
				
				if (next[1] < visited[next[0]]) {
					visited[next[0]] = next[1];
					pq.add(next);
				}
			}
		}
	} 
	
	public static void main(String[] args) throws Exception{
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		/**
		 *  - ToDo: 입력받는 과정 추가
     	 *  - 1번노드부터 존재한다고 가정
		 *  - 1번부터 10번까지의 최단거리를 구한다고 가정
		**/ 
		dijkstra(1, 10);
		bw.write("min distanct to 10: " + visited[10] + "\n");
		bw.flush();
		bw.close();
	}
}