[ 알고리즘 ] 최단거리 : Dijkstra Algorithm

1. Shortest Path

 

시작은 한군데지만 모든 목적지로 가는 shortest path를 다 구한다.

shortest path의 모든 부분은 shortest path이다.

 

이는 여러가지 버전이 있다.

1. 길이만 구하기
2. 길이와 Path 구하기
3. 가능한 여러개의 Path 구하기

 

2. Dijkstra Algorithm

 

이 알고리즘에 대해 설명해보겠다.

 

먼저 몇가지 정의를 하고가면

• R: 정답이 확정된 노드들의 집합
• B: Red Set에 있는 노드들만 거쳐서 갈 수 있는 노드들의 집합
• Dmin : 최단거리

 

1) 먼저 시작 노드부터 각 노드까지의 weight를 dim에 기록한다. 연결이 되어있지 않으면 ∞라고 기록된다.

2) 시작 노드를 R에 넣고 아래의 과정을 반복한다

1. R 밖에 있는 Dmin(u)들 중 가장 작은 weight를 가진 노드 u를 R에 넣는다.
2. R에 속하지 않은 다른 노드들 w에 대하여 갱신할 수 있는 값들을 갱신해준다. 갱신하는 방법은 현재 기록되어있는 Dmin(w)와 Dmin(u)+(u→w의 weight) 중 더 작은 값으로 갱신해주면 된다. 여기서 u는 1에서 새로 들어온 노드이다.

 

 

3. Dijkstra Algorithm - length

 

증명 (proof by induction)

Dijkstra Algorithm이 각 노드들의 최단길이를 찾을 수 있음을 증명해보자.

 

Base : n=1일 때는 Dmin(v0)=0 으로 주장이 성립한다.

Step :

어떤 시점에 집합 R=v0,v1,...,vi, B=w0,w1,...,wj이라고 하자. 

B 에 속한 노드들 중 Dmin(w) 값이 가장 작은 노드를 w라고 하고 이 노드를 집합 R에 추가하자.

 

* 가장 작은 노드를 R에 넣는게 정당한 이유
 w가 다음에 집합 R에 추가할 노드가 아니라면, 

R 집합을 거쳐서 오는길은 제일 짧은 것이 아니라는 뜻이므로 B 집합의 노드를 거쳐서 와야 더 짧다는 의미가 된다.

그 경로에서 처음으로 만난 B 집합의 노드를 반드시 존재하는데, 그 노드는 dmin(w) 보다 항상 크다.

따라서 모순이 발생하므로, w를 넣는 것이 정당하다.

 

 

R 집합에 B에 있던 노드 u를 추가하면, u를 통하는 더 저렴한 길이 생길 수 있기 때문에 집합 B의 Dmin(w) 값들을 모두 min(dmin(w),dmin(u)+g(u,w)) 값으로 갱신해줘야 한다. 

 

* u→w 만 확인해도되는 이유
 u→v→w 인 경우가 w까지의 최단거리라고 가정해보자. 

u는 방금 집합 R에 들어갔기 때문에, v는 그 이전에 집합 R에 들어가있었다.

즉, v가 R에 들어간 시점에는 u가 R 바깥에 있었다.

이 경우, source에서 v로 가는 최단경로 중에서 u를 안쓰고 R에 속하는 경로가 존재하게 된다.

따라서 u가 필요 없어지므로 가정에 모순이 된다.

그러므로 u→w인 경우만 따지는 것이 정당하다.

이미 u까지 가는 최단거리는 기록되어있어서 u→w 만 확인해도 된다.

 

4. Dijkstra Algorithm - path

증명(proof)

이제는 Dijkstra Algorithm를 통해 각 노드들의 실제 최단거리를 찾을 수 있는 최단거리 트리를 만들 수 있다는 것을 증명해보겠다.

 

모든 노드들은 최단경로 내에서 부모를 알고있다고 해보자. R에 u를 추가한 후에는 w 들의 최단거리를 갱신한다. 거리가 같은경우 기존 최단거리를 선택한다. 이렇게 최단거리 트리가 만들어진다.

 

 

5. Dijkstra Algorithm - all path

 

증명(proof)

이제는 Dijkstra Algorithm를 통해 각 노드들의 가능한 최단거리를 모두 찾을 수 있다고 가정해보자.

 

모든 노드들은 최단경로 내에서 부모를 알고있다고 해보자. R에 u를 추가한 후에는 w 들의 최단거리를 갱신한다. 거리가 같은경우 두 노드의 정보를 모두 저장하면 된다. 이렇게 최단거리 트리가 만들어진다.

 

6. 성능

노드의 개수 n 엣지의 개수 m 이라 하자.

• Source와 연결된 모든 정점마다 Edge Weight 를 dmin(v) 갱신 - O(n)
• R 에 Source 노드를 추가- O(1)
• R 바깥에 있는 dmin(u)들 중 가장 작은 값을 가진 노드 u를 찾아서 R에 넣는다. - O(logn)
• 그리고 R에 속하지 않는 노드들 w에 대해서  min(dmin(w),dmin(u)+g(u,w)) 값으로 집합 B(u와 인접)를 갱신시켜준다. 갱신하는 것도 O(log⁡n)이 걸리고, 이 행위를 모든 Edge들에 해야하므로 O(mlog⁡n)의 시간이 걸린다.

따라서 T(n)=O(mlogn)