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

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

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

어떤 변수 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다.

다익스트라 알고리즘은 각각의 꼭지점 v에 대해서 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다.

알고리즘 시작 시에 d[s] = 0이고, s가 아닌 다른 모든 꼭지점 v에 대해서는 d[v] = ∞ 로 놓아 다른 꼭지점에 대해서는 아직 최단 경로를 모른다는 사실을 표기한다.

알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.

출처 : 위키백과

- 음수 가중치가 없다고 가정

- s로부터 최단 경로의 길이를 이미 알아낸 노드들의 집합 S를 유지. 맨 처음엔 s = ∅

- Loop invariant : 

u  s 인 각 노드 u에 대해서 d(u)는 이미 s에 속한 노드들만 거쳐서 s로부터 u까지 가는 최단 경로의 길이

정리 : 

d(u) = min vs , d(v)인 노드 u에 대해서 d(u)는 s에서 u까지의 최단 경로의 길이이다.

증명 : (proof by comtradicition)

- 아니라고 하자, 그러면 s에서 u까지 다른 최단 경로가 존재한다.

- d(v) >= d(u) 이므로 모순

- d(u)가 최소인 노드 u  s 를 찾고, s에 u를 추가

- s가 변경되었으므로 다른 노드들의 d(v) 값을 갱신

d(v) = min {d(v), d(u)+w(u, v)}

즉, 에지(u, v)에 대해서 relaxation 하면 Loop invariant가 계속 유지됨

Dijkstra(다익스트라) 알고리즘 의사코드

Gijkstra(G, w, s){
	for each u ∈ v do
		do[u] <- ∞
		π[u] <- NIL
	end.
	s <- ∅
	d[s] <- 0
	while |s| < n do
		find u !∈ S with the minumum d[u] value;
		s <- s ∪ {u}
		
		for each v !∈ S adjacent to u do
			if(d[v] > d[u] + w(u, v) then
				d[v] <- d[u] + w(u, v)
				π[u] <- u
			end.
		end.
	end.
}

Dijkstra(G, w , s){
	INITIALIZE-SINGLE-SOURCE(G, s)
	S <- ∅
	Q <- V[G]
	while Q != ∅
		do u <- EXTRACT-MIN(∅)
			s <- S ∪ {u}
		for each vertex v ∈ Adj[u]
			do RELAX(u, v, w)
}

시간복잡도 : O(n^2)

예제를 통해 구현 : 소스 코드(Java)