Edge relaxation

For the edge from the vertex u to the vertex v, 
if d[u]+w(u,v)<d[v] is satisfied,
update d[v] to d[u]+w(u,v)

개념적으로 간단하게 정리하자면 DAG(Directed acyclic graph-엣지에 방향이 있고 순환이 없는 그래프) 에서 SSSP(single source shortest path) 를 구할때 source vertex 에서 v vertex 까지 도달하는 더 짧은 경로가 있다면 그 경로로 최단거리를 업데이트 한다는 말이다. 여기서 최단거리가 된다 라는 말이 아니라 업데이트 라고 한 까닭은 더 짧은 경로로 또 업데이트 될 수 있기 때문이다.

처음에 나온 문장을 해석하자면 계산된{source 에서 v vertex 까지 경로의 거리}가 {(source 에서 u vertex 까지의 거리) 더하기 (u vertex 에서 v vertex 까지의 거리)} 보다 크다면 source 에서 v vertex 까지의 최단 경로는 {(source 에서 u vertex 까지의 거리) 더하기 (u vertex 에서 v vertex 까지의 거리)} 로 업데이트 될 수 있다는 말이다.