Dijkstras algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes y Q=x,y, u, v! Vertices to relax s={s} Vertices with shortest path value Shortest path edge n[]=arrows Dijkstra's algorithm Assume all edges are non-negative Idea: Greedily relax out arcs of minimum cost nodes 10 46 0 Q=x,y, u, v) Vertices to relax Vertices with shortest path value Shortest path edge Ilvl=arrows ian williams, Spring 03Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 10 ’ 9 0 2 3 4 6 s 7 5 ’ ’ 2 x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 17 Dijkstra’s Algorithm Assume all edges are non-negative. Idea: Greedily relax out arcs of minimum cost nodes u v 1 10 10 ’ 9 2 3 4 6 s 0 7 5 5 2 ’ x y Q = {x,y,u,v} Vertices to relax S = {s} Vertices with shortest path value Shortest path edge Ȇ[v] = arrows Brian Williams, Spring 03 18