Dijkstra 알고리즘 증명

V는 모든 정점의 집합
Y는 최단 경로로 가는 정점의 집합

i는 노드의 갯수.

F(v1)=g(v,v1) v에서 v1으로 가는 가장 짧은 경로라고 한다.
n=2일때
v로 부터 가장 짧은 경로를 가지는 정점을 선택하므로 가장 먼저 Y에 들어가는 정점 u에 대하여
F(u)=g(v,u)가 성립한다.

n+1일 때,
Pu를 v로 부터 V-Y에 포함되는 정점 u로 가는 가장 짧은 경로의 길이라고 하고,
Wu를 Pu가 u에 닿기 전에 지나는 정점이라고 하면, Wu∈Y 리고, v로 부터 가장 가까운 n개의 정점중 하나이다.

그런데 F(u)는 v에서 u로 가는 가장 짧은 경로이므로 u는 v로부터 n+1번째로 가까운 정점이고, F(u)는 v로 부터 u로가는 가장 짧은 경로의 길이이다.

이것이 V-1번 반복되고, v로 부터 V의 모든 정점 u로 가는 최단거리 F(u)가 된다.