Dijkstras algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes Q=y, u, v! Vertices to relax S=s, xf Vertices with shortest path valu Shortest path edge nlv=arrows Dijkstras algorithm Assume all edges are non-negative Idea: Greedily relax out arcs of minimum cost nodes Q=u,vi Vertices to relax S=s,x, yh Vertices with shortest path value Shortest path edge Ilvl=arrows ian williams, Spring 03
Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 8 14 9 0 2 3 4 6 s 7 5 5 7 2 x y Q = {y,u,v} Vertices to relax S = {s, x} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 21 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 8 13 9 2 3 4 6 s 0 7 5 5 7 2 x y Q = {u,v} Vertices to relax S = {s, x, y} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 22
Dijkstras algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes Vertices to relax S=s, x, y, up Vertices with shortest path valu Shortest path edge nlv=arrows Dijkstras algorithm Assume all edges are non-negative Idea: Greedily relax out arcs of minimum cost nodes 416 Vertices to relax S=s, x, y, u, vI Vertices with shortest path value Shortest path edge Ilvl=arrows ian williams, Spring 03
8 9 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 9 0 2 3 4 6 s 7 5 5 7 2 x y Q = {v} Vertices to relax S = {s, x, y, u} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 23 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 8 9 9 2 3 4 6 s 0 7 5 5 7 2 x y Q = {} Vertices to relax S = {s, x, y, u, v} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 24
Dijkstra’ s Algorithm Repeatedly select minimum cost node and relax out arcs DIJKSTRA(G, w, S) 1. Initialize -Single-Source(G, S O( 3.Q←HG 4. while Q≠ dou← Extract-MinQ o0 or o(g v) 6. S←Smu w fib heap for each vertex v∈Adlu O() do relax(u, v, w) O(E) =O(V2+E) O(ViIgv+E) Outline Creating road maps for path p Exploring roadmaps Shortest paths Single Source Dijkstra;s algorith Informed search · Uniform cost search Greedy search · Beam search Hill climbing Avoiding adversaries lext Lecture) ian williams, Spring 03
26 25 DIJKSTRA(G,w,s) 1. Initialize-Single-Source(G, s) 2. S ĸ 3. Q ĸ V[G] 4. while Q 5. do u ĸ Extract-Min(Q) 6. S ĸ S {u} 7. for each vertex v Adj[u] 8. do Relax(u, v, w) Repeatedly select minimum cost node and relax out arcs O(V) O(V) * O(V) O(E) = O(V2+E) w fib heap = O(VlgV+E) Outline • planning • Shortest Paths – • – • • • • • • Dijkstra’s Algorithm or O(lg V) 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
Informed Search Extend search tree nodes to include path length g =8 5 Problem: Find the path to the goal G with the shortest path length g Brian Williams, Spring 03 Classes of search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found Iterative-Deepening Best-first Uniform-cost Using path "length" as a measure, informe Greedy finds "shortest path ian williams, Spring 03
Informed Search Extend search tree nodes to include path length g C 0 g = 8 S 2 3 G A 2 B 5 A 2 2 4 D 6 D C 4 6 D G 10 S 5 1 5 9 C G 8 9 C G 8 B Problem: Find the path to the goal G with the shortest path length g. Brian Williams, Spring 03 27 Classes of Search Blind Depth-First Systematic exploration of whole tree (uninformed) Breadth-First until the goal is found. Iterative-Deepening Best-first Uniform-cost Using path “length” as a measure, (informed) Greedy finds “shortest” path. A* Brian Williams, Spring 03 28
Uniform cost search spreads evenly from start goal Does uniform cost search find the shortest path? Uniform Cost path length dge cost Enumerates partial paths in order of increasing path length g May expand vertex more than once ian williams, Spring 03
Uniform cost search spreads evenly from start x x A B goal start Does uniform cost search find the shortest path? Brian Williams, Spring 03 29 Uniform Cost edge cost path length C 0 2 S 3 G A 2 2 4 D S 5 1 5 B Enumerates partial paths in order of increasing path length g. May expand vertex more than once. Brian Williams, Spring 03 30