IE172 – Algorithms in Systems EngineeringLecture 23Pietro BelottiDepartment of Industrial & Systems EngineeringLehigh UniversityMarch 16, 2009Shortest paths: definitions◮Given a digraph G = (V, A) and a weight w : A → R,◮Find th e shortest path from s to t, den oted δ(s, t).◮The w eight of the path is the sum of the weights of its arcs:w(P) =Pki=1wvi−1,vi◮δ(s, t) = ∞ if there is no path from s to t in GFour versions: find a path. . .◮Single-Source: . . . from a given s ∈ V to every node v ∈ V◮Single-Destination: . . . from every node v ∈ V to a givendestination node t ∈ V◮Single-Pair: . . . from given s ∈ V to given t ∈ V (to solvethis, you need to solve the the s ing le-source version)◮All-Pairs: . . . from every u ∈ V t o every node v ∈ VNegative Weight arcs◮In Minimum Spanning Tree, edges with negative weightare not a problem (t h ey are simply more likely to end up inthe solution)◮For shortest path, this is not the case:◮If we have a neg ative weight cycle, we can just keep goingaround it, and δ(s, v) = −∞ for all v on the cycle.◮Some algorithms work only if there are no ne gativeweight-arcs in the graphs−6233−7Relationships between shortest pathsLemma: Any subpath of a shortest path is a shortest path.Intuition. Consider the SP s → t, (s, v1, v2. . . , vp. . . , vq. . . , vk, t)running th rough two nodes vpand vq.If the sub-seq uence between vpand vqis not a shortest pathvp→ vq, then we could replace the sub-sequence with theshortest path vp→ vqand get an “outer” shorter path s → t.Lemma: Shortest p aths can’t contain cycles.◮(Single Source) sh ortest-path algorithms produce a label:d[v] = δ(s, v) (similarly to BFS)◮Initially d[v] = ∞, reduces as the algorithm go es, so alwaysd[v] ≥ δ(s, v) (similarly to BFS)◮Also p roduce labels π[v], predecessor of v on a shortestpath from s (similarly to BFS...)InitializingINIT-SINGLE-SOURCE-SP(V, s)1 d[s] ← 02 for each v in V \ {s}3 do d[v] ← ∞4 π[v] ← NIL◮The algorithms work by improving (lowering) the SPestimate d[v]◮This operation is called relaxing an arc (u, v)◮Can we improve the shortest-path est imate for v by goingthrough u and taking (u, v)?RELAX(u, v, w)1 if d[v] > d[u] + wuv2 then d[v] ← d[u] + wuv3 π[v] ← usd[v] = 56> 31d[u] = 22wuv= 9How To Do ItAll algorithms call INIT-SINGLE-SOURCE and RELAX, theydiffer in the order and number of th e calls to RELAX for an arc.Two extremely impor tant facts:Shortes t path weights obey the Triangle inequalityδ(s, v) ≤ δ(s, u) + wuv∀(u, v) ∈ A.The Relax operation only lowers p ath length estimatesd[v] ≥ δ(s, v) ∀v ∈ VIn other wo rds, d[v] is always an estimate from above. It startsat ∞ and decreases, but is never “better” than δ(s, v).LemmaPath Relaxation PropertyLet P = (v0, v1, . . . vk) be a shortest path from s = v0to vk. Ifthe arcs (v0, v1), (v1, v2), (vk−1, vk) are relaxedin that ordera,then d[vk] = δ(s, vk).aThere can be other relaxations in-between.Proof: by induction.◮True for i = 0, since d[s] = 0◮Assume d[vi−1] = δ(s, vi−1). By calling RELAX(vi−1, vi), wehave d[vi] = d[vi−1] + wvi−1,vi= δ(s, vi−1) + wvi−1,viandhence it must be a shortest path to vi(the label can neverchange)Wait. . . This doesn’t really give us an algorithm to find a SP.Bellman-Ford Algorithm◮Works w ith Negative-Weight Arcs◮Returns true is there are no negative-weight cyclesreachable from s,false otherwiseBELLMAN-FORD (V, E, w, s)1 INIT-SINGLE-SOURCE (V, s)2 for i ← 1 to |V| − 13 do fo r each (u, v) in E4 do RELAX(u, v, w)5 for each (u, v) in E6 do if d[v] > d[u] + wuv7 then return False8 return TrueAnalysisComplexity analysis: Θ(|V||E|)Correctness?◮Let v be reachable from s◮Let P = {v0, v1, . . . vk≡ v} be a shortest path to v◮Each iteration of the for loop relaxes all arcs◮The first iteration relaxes (v0, v1),The next (v1, v2). . . The k-th iteration relaxes (vk−1, vk)⇒ by th e path relaxation Lemma, d[v] = δ(s, v)Single Source S hortest Path on a DAGThis is a ve r y special case: there can be no cycles t o begin with.DAG-SHORTEST-PATHS (V, E, s, w)1 INIT-SINGLE-SOURCE (V, s)2 topologically sort the nodes (How?)3 for each u in topologically sorted V4 do fo r each v ∈ Adj[u]5 do RELAX(u, v, w)Correctness:◮Nodes are processed in topologically sorted order⇒ Arcs of any path are relaxed in order of appearance on path⇒ Arcs on any shortest path are relaxed in order⇒ By the path-relaxation lemma, the algorithm is correctDijkstra’s Algorithm◮Works only if the graph as no negative-weight arcs◮This is essentially a weighted-version of BFS◮Instead of a FIFO Queue (BFS) , use a priority queue◮Keys (in PQ) are the shortest-path weight estimates (d[v])◮We h ave two sets of nodes◮S: Nodes whose final shortest path weights are determined◮Q: Priority queue: V \ SDIJKSTRA(V, E, w, s)1 INIT-SINGLE-SOURCE (V, s)2 S ← ∅; Q ← V3 while Q 6= ∅4 do u ← EXTRACT-MIN(Q)5 S ← S ∪ {u}6 for each v ∈ Adj[u]7 do RELAX(u, v, w)How Dijkstra’s algorithm works456678910101111120∞∞∞∞∞∞∞456678910101111120∞∞∞∞∞67456678910101111120∞∞∞671516456678910101111120∞6715161718How Dijkstra’s algorithm works45667891010111112∞06715161718456678910101111120671516171828456678910101111120671516171828456678910101111120671516171828Dijkstra’s Algorithm◮Note: Looks a lot like Prim’s algorithm, but computingd[v], and using the shortest path weights as keys◮Dijkstra’s Algorithm is greedy, since it always chooses the“lightest” node in V \ S to add to S◮Analysis: Like Prim’s Algorithm, depends on the time ittakes to perform priority que ue op erations.◮Suppose we use a binary heap.◮How ma ny times is whole loop called: O(|E|)◮Inside loop, takes: (O(lg V)) to EXTRACT-MIN.◮Dijkstra’s algorithm runs in O(E lg V), with a binary heapimplementation.◮Bette r Heap implementations get it down to O(V lg V + E).All-Pairs S hortest Paths◮Given directed graph G = (V, E), w : E → R|E|. (To easenotation, we let V = {1, 2, . . . , n}.)◮Goal: Create an n × n matrix of shortest path distancesδ(i, j)◮We could run BELLMAN-FORD if negative weigh ts edges◮Running Time: O(|V|2|E|).◮We could run DIJKSTRA if no negative weight edges◮Running Time: (|V|3lg |V|) (with binary heapimplementation)◮We’ll see how to do slightly better, by ex ploiting ananalogy to matrix multiplicationNew Graph D ata