Weighted Graphs and Path Lengths 2|3 6 Graph G=<VE> Weight function w:E→ Path Path weight (p)=∑w(v1,v1) Shortest path weight b(u, v)=min w(p): u-P v) else oo Outline Creating road maps for path p Exploring roadmaps Shortest paths Single soure Dijkstra; s algorithm med searc · Uniform cost search Greedy search · Beam search Hill climbing Avoiding adversaries lext Lecture) Brian Williams, Spring 036 5 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 ’ Outline • planning • Shortest Paths – • – • • • • • • Creating road maps for path Exploring roadmaps: Single Source Dijkstra;s algorithm Informed search Uniform cost search Greedy search A* search Beam search Hill climbing Avoiding adversaries – (Next Lecture) Brian Williams, Spring 03 Brian Williams, Spring 03