Shortest PathsSingle Source DefinitionAll Pairs DefinitionCommentsNegative weight edgesRelaxation techniqueBellman-Ford AlgorithmRunning TimeProof of CorrectnessNegative weight cycleDAG shortest path algorithmRunning time ImprovementSlide 13Dijkstra’s AlgorithmRunning Time AnalysisRunning Time Analysis cont’dCompare Dijkstra’s algorithm to Prim’s algorithm for MSTSlide 18Slide 19Computing paths (not just distance)All pairs algorithms using single source algorithmsTwo adjacency matrix based algorithmsConceptual picturesRunning TimesJohnson’s AlgorithmReweightingComputing vertex weights h(v)Algorithm implementationShortest Paths•Definitions•Single Source Algorithms –Bellman Ford–DAG shortest path algorithm–Dijkstra•All Pairs Algorithms–Using Single Source Algorithms–Matrix multiplication–Floyd-Warshall•Both of above use adjacency matrix representation and dynamic programming–Johnson’s algorithm•Uses adjacency list representationSingle Source Definition•Input–Weighted, connected directed graph G=(V,E)•Weight (length) function w on each edge e in E–Source node s in V•Task–Compute a shortest path from s to all nodes in VAll Pairs Definition•Input–Weighted, connected directed graph G=(V,E)•Weight (length) function w on each edge e in E•We will typically assume w is represented as a matrix•Task–Compute a shortest path from all nodes in V to all nodes in VComments•If edges are not weighted, then BFS works for single source problem•Optimal substructure–A shortest path between s and t contains other shortest paths within it•No known algorithm is better at finding a shortest path from s to a specific destination node t in G than finding the shortest path from s to all nodes in VNegative weight edges•Negative weight edges can be allowed as long as there are no negative weight cycles•If there are negative weight cycles, then there cannot be a shortest path from s to any node t (why?)•If we disallow negative weight cycles, then there always is a shortest path that contains no cyclesRelaxation technique•For each vertex v, we maintain an upper bound d[v] on the weight of shortest path from s to v•d[v] initialized to infinity•Relaxing an edge (u,v)–Can we improve the shortest path to v by going through u?–If d[v] > d[u] + w(u,v), d[v] = d[u] + w(u,v)–This can be done in O(1) timeBellman-Ford Algorithm•Bellman-Ford (G, w, s)–Initialize-Single-Source(G,s)–for (i=1 to V-1)•for each edge (u,v) in E–relax(u,v);–for each edge (u,v) in E•if d[v] > d[u] + w(u,v)–return NEGATIVE WEIGHT CYCLE357-5321s35-1-5321sRunning Time•for (i=1 to V-1)–for each edge (u,v) in E•relax(u,v);•The above takes (V-1)O(E) = O(VE) time•for each edge (u,v) in E–if d[v] > d[u] + w(u,v)•return NEGATIVE WEIGHT CYCLE•The above takes O(E) timeProof of Correctness•If there is a shortest path from s to any node v, then d[v] will have this weight at end•Let p = (e1, e2, …, ek) = (v1, v2, v3, …, v,+1) be a shortest path from s to v–s = v1, v = vk+1, ei = (vi, vi+1)•At beginning of ith iteration, during which we relax edge ei, d[vi] must be correct, so at end of ith iteration, d[vi+1] will e correct–Iteration is the full sweep of relaxing all edges–Proof by inductionNegative weight cycle•for each edge (u,v) in E–if d[v] > d[u] + w(u,v)•return NEGATIVE WEIGHT CYCLE•If no neg weight cycle, d[v] ≤ d[u] + w(u,v) for all (u,v)•If there is a negative weight cycle C, for some edge (u,v) on C, it must be the case that d[v] > d[u] + w(u,v).–Suppose this is not true for some neg. weight cycle C–sum these (d[v] ≤ d[u] + w(u,v)) all the way around C–We end up with sum(d[v]) ≤ sum(d[u]) + weight(C) •This is impossible unless weight(C) = 0•But weight(C) is negative, so this cannot happen–Thus for some (u,v) on C, d[v] > d[u] + w(u,v)DAG shortest path algorithm•DAG-SP (G, w, s)–Initialize-Single-Source(G,s)–Topologically sort vertices in G–for each vertex u, taken in sorted order•for each edge (u,v) in E–relax(u,v);35-4381s54Running time Improvement•O(V+E) for the topological sorting •We only do 1 relaxation for each edge: O(E) time–for each vertex u, taken in sorted order•for each edge (u,v) in E–relax(u,v);•Overall running time: O(V+E)Proof of Correctness•If there is a shortest path from s to any node v, then d[v] will have this weight at end•Let p = (e1, e2, …, ek) = (v1, v2, v3, …, v,+1) be a shortest path from s to v–s = v1, v = vk+1, ei = (vi, vi+1)•Since we sort edges in topological order, we will process node vi (and edge ei) before processing later edges in the path.Dijkstra’s Algorithm•Dijkstra (G, w, s)•/* Assumption: all edge weights non-negative */–Initialize-Single-Source(G,s)–Completed = {};–ToBeCompleted = V;–While ToBeCompleted is not empty•u =EXTRACT-MIN(ToBeCompleted);•Completed += {u};•for each edge (u,v) relax(u,v);15574321sRunning Time Analysis•While ToBeCompleted is not empty–u =EXTRACT-MIN(ToBeCompleted);–Completed += {u};–for each edge (u,v) relax(u,v);•Each edge relaxed at most once: O(E)•Need to decrease-key potentially once per edge•Need to extract-min once per nodeRunning Time Analysis cont’d•O(E) edge relaxations•Priority Queue operations–O(E) decrease key operations–O(V) extract-min operations•Three implementations of priority queues–Array: O(V2) time•decrease-key is O(1) and extract-min is O(V)–Binary heap: O(E log V) time assuming E >= V•decrease-key and extract-min are O(log V)–Fibonacci heap: O(V log V + E) time •decrease-key is O(1) amortized time and extract-min is O(log V)Compare Dijkstra’s algorithm to Prim’s algorithm for MST•Dijsktra–Priority Queue operations•O(E) decrease key operations•O(V) extract-min operations•Prim–Priority Queue operations•O(E) decrease-key operations•O(V) extract-min operations•Is this a coincidence or is there something more here?Proof of Correctness•Assume that Dijkstra’s algorithm fails to compute length of all shortest paths from s•Let v be the first node whose shortest path length is computed incorrectly•Let S be the set of nodes whose shortest paths were computed correctly by Dijkstra prior to adding v to the processed set of nodes.•Dijkstra’s algorithm has used the shortest path from s to v using only nodes in S when it added v to S.•The shortest path to v must include one node not in S•Let u