dijkstra 알고리즘

최단경로를 찾는 알고리즘이다.

가정

1. 음수 가중치가 존재하지 않는다

2. 시작점 s로부터 최단 경로를 알아낸 노드들의 집합을 S

3. S에 속하지 않는 노드들 u에 대해, d[u]는 S의 노드들을 거쳐 u까지 오는 경로 중 최단 경로이다.

Theorem. U에 속하는 모든 노드들 중 d[u]가 노드 u에 대해,  d[u]는 s에서 u까지의 최단 경로이다.

Proof) 

s에서 u까지 다른 최단 경로가 존재한다고 하자. 이 때, 가정 3에 의해, S에 속하지 않는 점 v를 지나게되는데, 

d[u] = d[v] + u(v,w)가 된다. 하지만 d[u]<=d[v]이므로 모순이다. 따라서 위 이론이 성립한다.

알고리즘 순서

1. minimum d[u]를 찾는다.

2. u와 연결된, d[v]를 update한다. ( 가정3에 의해, S가 변경되었기 때문에 update해줘야 된다)