Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Readings01/13/19Shortest Path ProblemsThe Shortest-Path problems in a directed and weighted graph G(V, E, w) include:Single-source shortest-path problem: find a shortest path from a given source s to every vertex v  V.Single-destination shortest-path problem: find a shortest path to a given destination d from every vertex v  V. By reversing the direction of each edge,  Single-source shortest-path problem.Single-pair (u, v) shortest-path problem. All-pairs shortest-path problem: For each vertex s  V, call single-source shortest-path algorithm.Non-negative weight vs. negative weight01/13/19DefinitionsThe weight of a path p = <v0, v1, ..., vk> iskiiivvwpw11),()(otherwisevupvupwvup)...)((}:)(min{),(The shortest-path weight from u to v isA shortest path from vertex u to vertex v is then defined as any path p with w(p) = (u, v)01/13/19Subpath Optimality PropertyLet p=<v1,v2, …, vk> be a shortest path from vertex v1 to vertex vk. Let pij=<vi, vi+1, …, vj> be the subpath of p from vertex vi to vertex vj. Then pij is a shortest path from vi to vj.Representation of a shortest path. There is no need to store the path. We only need to store the predecessor at each node.01/13/19Relaxation TechniqueThe idea of shortest path algorithms is based on the relaxation technique:We initialize distance to the source to Initialize-Single-Source(G, s)1. for each vertex v  V[G] do2. v.d := 3. v. := nil4. s.d := 0We adjust (reduce) the distance whenever we visit an edgeRelax(u, v, w)1. if v.d > u.d + w(u, v)2. then v.d := u.d + w(u, v)3. v. := u // set parent pointer01/13/19Dijkstra’s Single-Source Shortest Path Alg.5 925 725 625 62Relax:SQThe idea of the algorithm is similar to Prim’s MST algorithm:•Use a greedy approach•Use a priority queue Q, the key is the distance to the source.•Processed vertices are removed from Q and stored in a set S01/13/19Dijkstra’s Single-Source Shortest Path Alg.Dijkstra-SP(G, w, s)1. Initialize-Single-Source(G, s)2. S := 3. Q := V[G]4. while Q   do5. u := Extract-Min(Q)6. S := S  {u}7. for each vertex v  u.adj do8. Relax(u, v, w)0105219326471050105219326478514010521932647785130105219326477859010521932647701/13/19Running Time of Dijkstra’s AlgorithmThe running time depends on how we implement QIf we use a simple array to implement Q•Extract-Min takes O(|V|)•while-loop repeats O(|V|) times•the total # of vertices in adjacency lists = O(|E|)•The total running time is O(|V|2 + |E|)If we use a binary heap to implement Q•Build heap takes O(|V|)•Extract-Min takes O(lg|V|)•v.d := u.d+w(u, v) in Relax decrease-key: O(lg|V|)•The total running time is O((|E|+|V|)lg|V|)= O(|E|lg|V|) if the graph is connected.If we use a Fibonacci heap to implement Q•The total running time is O(|V|lg|V| + |E|)01/13/19Correctness of AlgorithmsFor all predefined inputs (precondition), the algorithm produces correct outputs (postconditions).Partial Correctness•If the preconditions are satisfied andif the program terminates,•then the postconditions are satisfied.•Core: loop invariant and inductionTermination•If the preconditions are satisfied•then the algorithm terminates in finite steps•strictly decreasing order on finite set01/13/19Correctness of Dijkstra’s AlgorithmPartial correctness and terminationPrecondition:weighted graph G = (V, E, W) and s  V and w  0Postcondition:d[u] = (s, u)Loop-invariant:(u) (u  S  d[u] = (s, u))S = V when exiting the loopTherefore the postcondition is true.Use mathematical induction:Step 1: For iteration 1, S = {s} and d[s] = (s, s) = 0, the loop invariant is true.01/13/19Correctness of Dijkstra’s Algorithm (contd.)Step 2: We assume that it is true when S has k elements and wish to prove, it is still true when another element (k+1)th u is added to S. sxzyuSVertex u is not connected to S.This is not possible, otherwisey should be chosen in step 5by extract-min(Q)sxzuSSince x and z are in S and d[x] = (s, x) and d[z] = (s, z)u must have been relaxed fromx and z and d[u] = min (d[x]+w(x,u), d[z]+w(z,u))...01/13/19Correctness of Dijkstra’s Algorithm: TerminationThe termination property can be proved based on the facts:•There are finite number of elements in QInitially: |Q| = |V|.•The size of Q decrease by one in each iteration, therefore the size of the Q decreases strictly.•Conclusion: the algorithm will terminate.01/13/19Negative-Weight EdgesWhen do we need a graph with negative-weight edges?0 ?3523-66-3-4352It will be -, if there is a "negative-weight cycle".In the following discussion, we will assume thereis not a "negative-weight cycle" in the given graph.sd0 ?2-8 3dsWhat is the shortest distance from s to d?01/13/19Bellman-Ford's Single-Source AlgorithmDijkstra’s algorithm: non-negative weight only. Bellman-Ford’s algorithm: also negative weights.Bellman-Ford(G, w, s)1. Initialize-Single-Source(G, s)2. for i := 1 to |V| - 1 do3. for each edge (u, v)  E do4. Relax(u, v, w)5. for each vertex v  u.adj do6. if d[v] > d[u] + w(u, v)7. then return False // there is a negative cycle8. return True // there is not a negative cycleTotal running time: O(|V|*|E|)O(|V|)O(|V|*|E|)O(|E|)01/13/19Bellman-Ford's Algorithm: Example06795-387-42sy zxt-2initializationafter pass 1 after pass 26706795-387-42sy zxt-267406795-387-422y zxt-2after pass 3 after pass 427406795-387-422y zxt-227406795-387-42-2y zxt-2The order of Relax in each pass:(t, x), (t, z), (x, t), (y, x), (y, t), (y, z), (z, x), (z, s), (s, t), (s, y)01/13/19Bellman-Ford's Algorithm: CorrectnessLemmaLet G = (V, E, W) be a weighted, directed graph;Let G contain no negative-weight cycles that are reachable from the source s;ThenAfter the |V| - 1 passes (iteration of the outer for-loop), we have d[v] = (s, v) for all vertices v that are reachable from s.For each vertex v, there is a path from s to v, if and only if the algorithm terminates with d[v] < .01/13/19Bellman-Ford's Algorithm: CorrectnessTheoremIf G contains no negative-weight cycles that are reachable from the source s, then the algorithm will return True and we have d[v] = (s, v) for all vertices v that are reachable from s.If the