Relax Bounds to shortest path Relax(u, v) Relax(u, v) 7 Relax(u, v, w) 1. if du]+w(u, v<dvI 2 dod/vy/←a]+ v7← Properties of relaxing bounds 2 2 Relax(u, v) Relax(u, v) (2 After calling Relax(u, v, w) d]+w(u,v)≥y d remains a shortest path upperbound after repeated calls Relax Once d[v] is the shortest path its value persists ian williams, Spring 03Relax Bounds to Shortest Path u v u v 2 2 5 9 5 6 Relax(u, v) Relax(u, v) u v u v 2 2 5 7 5 6 Relax (u, v, w) 1. if d[u] + w(u,v) < d[v] 2. do d[v] ĸ d[u] + w(u,v) 3. ʌ[v] ĸ u Brian Williams, Spring 03 13 Properties of Relaxing Bounds u v u v 2 2 5 9 5 6 Relax(u, v) Relax(u, v) u v u v 2 2 5 9 5 6 After calling Relax(u, v, w) • d[u] + w(u,v) • d[v] d remains a shortest path upperbound after repeated calls to Relax. Once d[v] is the shortest path its value persists Brian Williams, Spring 03 14