13.pdf

개념적인 이야기

dx(y) : x에서 y까지의 최소 cost

dx(y) = min_v { c(x,v) + dv(y) }

x에서 y까지의 경로는

x에서 y까지 갈때 거쳐가는 x의 이웃 v라는 곳이 있다고 하면

x에서 x의 이웃 v까지 최단 거리하나, v에서 y까지의 거리를 합한 것 중에서 가장 작은 값이 dx(y)이다.