Introduction To Algorithms CS 445This LectureShortest PathShortest-Path ProblemsNegative Weights and Cycles?RelaxationDijkstra's AlgorithmDijkstra’s Pseudo CodeDijkstra’s ExampleDijkstra’s Example (2)Dijkstra’s Example (3)Dijkstra’s Running TimeBellman-Ford AlgorithmSlide 14Bellman-Ford ExampleSlide 16Introduction To AlgorithmsCS 445Discussion Session 6Instructor: Dr Alon EfratTA : Pooja Vaswani03/21/20052This Lecture•Single-source shortest paths in weighted graphs–Shortest-Path Problems–Properties of Shortest Paths, Relaxation–Dijkstra’s Algorithm–Bellman-Ford Algorithm3Shortest Path•Generalize distance to weighted setting•Digraph G = (V,E) with weight function W: E  R (assigning real values to edges)•Weight of path p = v1  v2  …  vk is•Shortest path = a path of the minimum weight•Applications–static/dynamic network routing–robot motion planning–map/route generation in traffic111( ) ( , )ki iiw p w v v4Shortest-Path Problems•Shortest-Path problems–Single-source (single-destination). Find a shortest path from a given source (vertex s) to each of the vertices. –Single-pair. Given two vertices, find a shortest path between them. Solution to single-source problem solves this problem efficiently, too.–All-pairs. Find shortest-paths for every pair of vertices. Dynamic programming algorithm.5Negative Weights and Cycles?•Negative edges are OK, as long as there are no negative weight cycles (otherwise paths with arbitrary small “lengths” would be possible)•Shortest-paths can have no cycles (otherwise we could improve them by removing cycles)–Any shortest-path in graph G can be no longer than n – 1 edges, where n is the number of vertices6Relaxation•For each vertex v in the graph, we maintain v.d(), the estimate of the shortest path from s, initialized to  at the start•Relaxing an edge (u,v) means testing whether we can improve the shortest path to v found so far by going through uu vvu22 Relax(u,v)u vvu22 Relax(u,v)Relax (u,v,G)if v.d() > u.d()+G.w(u,v) then v.setd(u.d()+G.w(u,v)) v.setparent(u)7Dijkstra's Algorithm•Non-negative edge weights•Greedy, similar to Prim's algorithm for MST•Like breadth-first search (if all weights = 1, one can simply use BFS)•Use Q, a priority queue ADT keyed by v.d() (BFS used FIFO queue, here we use a PQ, which is re-organized whenever some d decreases)•Basic idea–maintain a set S of solved vertices–at each step select "closest" vertex u, add it to S, and relax all edges from u8Dijkstra’s Pseudo Code•Input: Graph G, start vertex srelaxing edgesDijkstra(G,s)01 for each vertex u  G.V()02 u.setd(03 u.setparent(NIL)04 s.setd(0)05 S // Set S is used to explain the algorithm06 Q.init(G.V()) // Q is a priority queue ADT07 while not Q.isEmpty()08 u  Q.extractMin()09 S S {u} 10 for each v  u.adjacent() do11 Relax(u, v, G)12 Q.modifyKey(v)9Dijkstra’s Example  su vyx10512 394 672  su vyx10512 394 672Dijkstra(G,s)01 for each vertex u  G.V()02 u.setd(03 u.setparent(NIL)04 s.setd(0)05 S 06 Q.init(G.V())07 while not Q.isEmpty()08 u  Q.extractMin()09 S S {u} 10 for each v  u.adjacent() do11 Relax(u, v, G)12 Q.modifyKey(v)10Dijkstra’s Example (2)u v  syx10512 394 672  su vyx10512 394 672Dijkstra(G,s)01 for each vertex u  G.V()02 u.setd(03 u.setparent(NIL)04 s.setd(0)05 S 06 Q.init(G.V())07 while not Q.isEmpty()08 u  Q.extractMin()09 S S {u} 10 for each v  u.adjacent() do11 Relax(u, v, G)12 Q.modifyKey(v)11Dijkstra’s Example (3)  u vyx10512 394 672  u vyx10512 394 672Dijkstra(G,s)01 for each vertex u  G.V()02 u.setd(03 u.setparent(NIL)04 s.setd(0)05 S 06 Q.init(G.V())07 while not Q.isEmpty()08 u  Q.extractMin()09 S S {u} 10 for each v  u.adjacent() do11 Relax(u, v, G)12 Q.modifyKey(v)12Dijkstra’s Running Time•Extract-Min executed |V| time•Decrease-Key executed |E| time•Time = |V| TExtract-Min + |E| TDecrease-Key•T depends on different Q implementationsQ T(Extract-Min)T(Decrease-Key) Totalarray (V)(1)(V 2)binary heap(lg V)(lg V)(E lg V)Fibonacci heap(lg V)(1) (amort.)(V lgV + E)13Bellman-Ford Algorithm•Dijkstra’s doesn’t work when there are negative edges:–Intuition – we can not be greedy any more on the assumption that the lengths of paths will only increase in the future•Bellman-Ford algorithm detects negative cycles (returns false) or returns the shortest path-tree14Bellman-Ford AlgorithmBellman-Ford(G,s)01 for each vertex u  G.V()02 u.setd(03 u.setparent(NIL)04 s.setd(0)05 for i  1 to |G.V()|-1 do06 for each edge (u,v)  G.E() do07 Relax (u,v,G) 08 for each edge (u,v)  G.E() do09 if v.d() > u.d() + G.w(u,v) then 10 return false11 return true15Bellman-Ford Example5  szy678-3729-2xt-4  szy678-3729-2xt-45  szy678-3729-2xt-45  szy678-3729-2xt-4516Bellman-Ford Example  szy678-3729-2xt-4•Bellman-Ford running time:–(|V|-1)|E| + |E| =