IT/알고리즘
최단경로(shortest path problem)-2
다날92
2018. 1. 10. 17:56
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가 계속 유지됨