Weighted graphs and Path Lengths 7 graph h G=<VE> Weight function :E→9 Path p=< Path weight (p)=∑w(v;12V1) Shortest path weight b(u, v)=min w(p): u-Pv)else oo
u v 1 x y 2 10 5 7 9 2 3 4 6 s Weighted Graphs and Path Lengths Graph G = <V, E> Weight function w: E →ℜ Path p = < vo, v1, … vk > Path weight w(p) = Σ w(vi-1,vi) Shortest path weight δ(u,v) = min {w(p) : u →p v } else ∞
Single source shortest path 7 Problem: Compute shortest path to all vertices from source s
Single Source Shortest Path u v 1 x y 2 10 5 7 9 2 3 4 6 s Problem: Compute shortest path to all vertices from source s
Single source shortest path Problem: Compute shortest path to all vertices from source s estimate dvI estimated shortest path length from s to v
Single Source Shortest Path 8 9 u v 1 5 7 x y 2 0 10 5 7 9 2 3 4 6 s Problem: Compute shortest path to all vertices from source s • estimate d[v] estimated shortest path length from s to v
Single source shortest path 7 Problem: Compute shortest path to all vertices from source s estimate dvI estimated shortest path length from s to v predecessor v final edge of shortest path to v induces shortest path tree
Single Source Shortest Path 8 9 u v 1 5 7 x y 2 0 10 5 7 9 2 3 4 6 s Problem: Compute shortest path to all vertices from source s • estimate d[v] estimated shortest path length from s to v • predecessor π[v] final edge of shortest path to v • induces shortest path tree
Single Destination Shortest path 8 10 08 y x Problem: Compute shortest path from all vertices to goal g estimate hv estimated shortest path length from s to v descendant bv first edge of shortest path from v to g induces shortest path tree
9 8 v u 1 7 5 y x 2 0 10 5 7 9 6 4 3 2 g Single Destination Shortest Path Problem: Compute shortest path from all vertices to goal g • estimate h[v] estimated shortest path length from s to v • descendant b[v] first edge of shortest path from v to g • induces shortest path tree