최단경로(shortest path problem)-2

Bellman-Ford 알고리즘

한가지가능의예일뿐 과정은 다를수 있다.

Dijkstra의 알고리즘

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

- s로뷰토의 최단경로의 길이를 이미 알아낸 노드들의 집합 s를 유지. 맨 처음엔 S={공징합}.

- Loop invariant 

: S에 포함되지 않는 u에 대해서 d(u)는 이미 s에 속한 노드들만 거쳐서 s로부터 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가 계속 유지됨