算法课件Lecture9章节.pptVIP

Dijkstra’s Algorithm andDifference Constraints System Dijkstra’s algorithm Problem solved Correctness Time complexity Similarities to BFS and PRIM Difference constraints system Constraint graph Problem Solved by Dijkstra’s Single-source shortest-paths problem Edge weight =0 Input: A graph G=(V, E) and a source s, and a nonnegative function w: E?R+ Output: For each vertex v, shortest path weight d(s,v), and a shortest path if exists. Compared to PRIM DIJKSTRA(G,w,s) for each u ?V[G] do d[u]?? ?[u]?NIL d[s]?0 S?? Q?V[G] while Q?? do u?EXTRACT-MIN(Q) S?S?{u} for each v ?Adj[u] do if v ? Q and d[u]+w(u,v)d[v] then ?[v]?u d[v]?d[u]+w(u,v) Dijkstra’s Algorithm - example Initial Graph Dijkstra’s Algorithm - Operation Initial Graph Dijkstra’s Algorithm - Operation Dijkstra’s Algorithm - Operation Dijkstra’s Algorithm - Operation Dijkstra’s Algorithm - Operation Dijkstra’s Algorithm - Operation Correctness of Dijkstra’s Theorem 24.6 Dijkstra’s algorithm, run on a weighted,directed graph G=(V, E), with non-negative weight function w and source s, terminates with d[u]= d(s,u) for all vertices u?V. Proof (by contradiction) Since S=V in the end, we only need to prove that for each vertex v added to S, there holds d[v]= d(s, v) when v is added to S. Suppose that u is the first vertex for which d[u] 1 d(s, u) when it was added to S Note u is not s because d[s] = 0= d(s, s) There must be a path s?...?u, since otherwise d[u]= d(s, u) = ￥. Since there’s a path, there must be a shortest path (note there is no negative cycle). Dijkstra’s Algorithm - Proof Let s?x?y?u be a shortest pathfrom s to u, where at the moment u is chosen to S, x is in S and y is the first outside S When x was added to S, d[x] = d(s, x) Edge x?y was relaxed at that time, so at time u is chosen, d[y] = d(s, y) Dijkstra’s Algorithm - Proof So, d[y]= d(s, y) ￡ d(s, u) ￡ d[u] But, when we chose u,both u and y are in Q,so d[u] ￡ d[y] (otherwise we wo