[알고리즘 / Java] 최단 경로 구하기 - 다익스트라 알고리즘 (Dijkstra)

최단 경로 알고리즘

그래프 G = (V, E)가 주어지고 여기서 E는 가중치를 가진 유향 간선들의 집합이다.

임의의 경로는 연속된 간선들로 구성된다. 경로를 구성하는 간선들의 가중치의 합이 해당 경로의 길이가 된다.

다익스트라 알고리즘은 음의 가중치가 없는 경우에 사용이 가능하다.

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

시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.

그리디를 이용한 알고리즘으로 Prim이랑 유사한 방법이라고 보면된다.

 

구현하기

Dijkstar(s, A, d) s : 시작 정점 A : 인접 행렬 D : 시작 정점에서의 거리 정점의 집합 <- s for 모든 정점 v    D[v] <- A[s][v] //인접하지 않는 정점의 비용은 INF while 정점의 집합 != 모든 정점의 집합    D[w]가 최소인 정점을 선택 // w : 모든 정점의 집합 중 정점의 집합에 속하지 않는 정점 w    정점의 집합 <- union(w, 정점의 집합)    for(w에 인접함 모든 미방문 정점 v)       D[v] <- min(D[v], d[w] + a[w][v]) //경유지를 거쳐가는게 유리한지 아닌지 판별하기

 

프림 알고리즘과 매우 유사하지만 프림 알고리즘에서는 d[v]가 정점 v를 신장트리에 연결하는 최소비용을 위해서 사용되지만 다익스트라에서는 정점r에서 정점 v에 이르는 최단 거리가 된다는 점이 다르다.

 

다음과 같은 그래프가 있을 때 동작 과정을 살펴 보자.

 

시작 정점은 1이 될 것이다. 그렇다면 D는 다음과 같이 업데이트된다.

이 중 가장 작은 값은 4번 정점으로의 1이기 때문에 4번 정점에 인접한 미방문 정점에 대해서 값이 업데이트된다.

D[5] > D[4] + A[4][5] 이기 때문에 D[5]는 D[4] + A[4][5]인 3으로 업데이트가 되고 다음과 같이 변화한다.

4에서 더 이상 방문할 정점이 없으므로 다시 한번 D[w] 가 최소인 정점을 선택하게된다.

이 경우 2가 선택된다.

2에서 인접한 정점은 4인데 4는 이미 방문한 정점이기 때문에 탐색을 진행하지 않게된다.

3번 정점 역시 이와 같은 방식으로 지나가게 되어 모든 정점을 방문하게 된다.

 

Priority Queue로 구현

현재 노드에서 갈 수 있는 노드 중 가장 작은 D값을 가진 노드를 찾기 위해서 최악의 경우에는 O(N)의 시간이 걸리게 된다.

그리고 만약 모든 노드들이 그러한 경우에 처하게 되면 시간 복잡도는 O(N^2)가 될 수도 있다.

이런 경우에 대비하여 우선순위 큐를 사용하게 되면 시간 복잡도를 줄일 수 있다.

참고로 우선순위 큐의 삽입 삭제의 시간 복잡도는 O(log N)이다.

이 과정을 반복하게 된다면 우선순위 큐를 사용하였을 때 다익스트라의 시간 복잡도는 O(ElogN)이 된다.

 

static void dijkstra(int start) {
		PriorityQueue<Data> pq = new PriorityQueue<>();
		pq.add(new Data(start, 0));
		visited[start] = true;
		while(!pq.isEmpty()) {
			Data now = pq.poll();
			for(Data next : graph[now.idx]) {
				if(distances[next.idx] > distances[now.idx] + next.value) {
					distances[next.idx] = distances[now.idx] + next.value;
					pq.add(new Data(next.idx, distances[next.idx]));
				}
			}
		}
		
	}


}

class Data implements Comparable<Data>{
	int idx;
	int value;
	
	
	public Data(int idx, int value) {
		super();
		this.idx = idx;
		this.value = value;
	}


	@Override
	public int compareTo(Data o) {
		return this.value - o.value;
	}
	
	
}