Graphs(3) - Dijkstra's algorithm

Shortest Paths Problems

Input : A graph with weights

Output : shortest path

 

어떻게 해야 shortest path를 계산할 수 있을까?

 

Definitions

δ(s, u) -> vertex s에서 u까지의 가장 짧은 거리

w(u, v) -> u에서 v를 연결하는 edge의 weight. 그러한 edge가 없다면 무한대로 정의된다.

 

 

 

Algorithm by Dijkstra

vertex s에서 출발하여 다른 모든 vertices들을 방문하는 shortest path를 찾아보자.

 

• visited vertices들을 가지고 있는 set S를 만든다. 그리고 size n인 array D도 만든다. array D에는 s로부터의 현재 estimate된 거리를 담아둔다.
• 처음에는 S는 비어 있고, D[s] = 0이다. 
• 각 iteration마다 u에서 가장 가까운 거리에 있는 vertex를 S에 집어넣는다. 그리고 D를 업데이트 하기 위하여 relax operation을 시행한다.

Relax Operation

u의 이웃인 v에 대한 거리를 D에 업데이트 한다.

Relax operation

 

 

Dijkstra Example

Example

Correctness of Dijkstra

어떠한 vertex u가 S에 추가되면, d(s,u) = δ(s, u)이다. 그렇기 때문에 이 알고리즘이 올바르게 동작하는 것이다.

 

Proof

key idea :

s에서 y로 가는 shortest path P 안에 node x가 있다고 가정하자.

그렇다면 그 P안에 있는 s에서 x로가는 path는 s에서 x로 가는 shortest path이다.

 

Induction :

• Base case : u=s일때는 자명하다.
• Induction Hypothesis : 현재 S에 대해서는 모두 성립한다고 가정하자.
• 이제 새로운 u를 S에 추가할 때, d(s,u) = δ(s, u)임을 보이면 된다.
• s에서 u로가는 shortest path에서 S 경계 안쪽에 있는 x와 그 x와 연결된 바깥에 있는 y가 존재한다. (그림 참조)

• d(s,y) ≤ d(s,x) + w(x,y) = δ(s, x) + w(x,y) = δ(s, y)
• δ(s, y)는 최단 경로이므로 d(s,y) = δ(s, y)이다. 
• d(s,y) = δ(s, y) ≤ δ(s, u) ≤d(s,u). 그러나 y보다 u가 먼저 S에 추가되었으므로 d(s,u)≤d(s,y)이다.
• 따라서 d(s,u) = δ(s,u)이다.

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업