**Unformatted text preview:**

15.082J & 6.855J & ESD.78J September 23, 2010 Dijkstra’s Algorithm for the Shortest Path Problem21 Single source shortest path problem 2 3 4 5 6 2 4 21 3 4 2 3 2 1 ∞ ∞ ∞ ∞ ∞ Find the shortest path from a source node to each other node. Assume: (1) all arc lengths are non-negative (2) the network is directed (3) there is a path from the source node to all other nodesOverview of today’s lecture Dijkstra’s algorithm animation proof of correctness (invariants) time bound A surprising application (see the book for more) A Priority Queue implementation of Dijkstra’s Algorithm (faster for sparse graphs) 3A Key Step in Shortest Path Algorithms In this lecture, and in subsequent lectures, we let d( )denote a vector of temporary distance labels. d(i) is the length of some path from the origin node 1to node i. Procedure Update(i) for each (i,j) ∈ A(i) do if d(j) > d(i) + cij then d(j) : = d(i) + cij and pred(j) : = i; Update(i) used in Dijkstra’s algorithm and in the labelcorrecting algorithm 4Update(7) d(7) = 6 at some point in the algorithm, because of the path 1-8-2-7 11 8 1 3 2 1 8 2 9 7 0 1 4 8 no change 7 6 9 5 3 2 1 3 Suppose 7 is incident to nodes 9, 5, 3, with temporary distance labels as shown. We now perform Update(7). 5On Updates Note: distance labels cannot increase in an update step. They can decrease. 11 8 2 1 3 2 1 8 2 7 5 1 9 7 9 0 1 4 6 3 3 8 no change We do not need to perform Update(7) again, unless d(7) decreases. Updating sooner could not lead to further decreases in distance labels. In general, if we perform Update(j), we do not do so again unless d(j) has decreased. 6Dijkstra’s Algorithm Let d*(j) denote the shortest path distance from node 1 to node j. Dijkstra’s algorithm will determine d*(j) for each j, in order of increasing distance from the origin node 1. S denotes the set of permanently labeled nodes. That is, d(j) = d*(j) for j ∈ S. T = N\S denotes the set of temporarily labeled nodes. 7Dijkstra’s Algorithm S : = {1} ; T = N – {1}; d(1) : = 0 and pred(1) : = 0; d(j) = ∞ for j = 2 to n; update(1); while S ≠ N do (node selection, also called FINDMIN) let i ∈T be a node for which d(i) = min {d(j) : j ∈ T}; S : = S ∪ {i}; T: = T – {i}; Update(i) Dijkstra’s Algorithm Animated 8Invariants for Dijkstra’s Algorithm 1. If j ∈ S, then d(j) = d*(i) is the shortest distance from node 1 to node j. 2. (after the update step) If j ∈ T, then d(j) is the length of the shortest path from node 1 to node j in S ∪ {j}, which is the shortest path length from 1 to j of scanned arcs. Note: S increases by one node at a time. So, at the end the algorithm is correct by invariance 1. 91 Verifying invariants when S = { 1 } 2 3 4 5 6 2 4 21 3 4 2 3 2 1 0 2 ∞ ∞ Consider S = { 1 } ∞4 and after update(1) 1. If j ∈ S, then d(j) is the shortest distance from node 1 to node j. 2. 3. If j ∈ T, then d(j) is the length of the shortest path from node 1 to node j in S ∪ {j}. 10Verifying invariants Inductively 2 6 Assume that 23 24 45 the invariants 622 0are true before 61 a ∞a node 1 24selection 3 d(5) = min {d(j) : j ∈ T}. 3 4 Any path from 1 to 5 passes through a node k of T. The path to node k has distance at least d(5). So d(5) = d*(5). Suppose 5 is transferred to S and we carry out Update(5). Let P be the shortest path from 1 to j with j ∈ T. If 5 ∉ P, then invariant 2 is true for j by induction. If 5 ∈ P, then invariant 2 is true for j because of Update(5). 11A comment on invariants It is the standard way to prove that algorithms work. Finding the best invariants for the proof is often challenging. A reasonable method. Determine what is true at each iteration (by carefully examining several useful examples) and then use all of the invariants. Then shorten the proof later. 12Complexity Analysis of Dijkstra’s Algorithm Update Time: update(j) occurs once for each j, upon transferring j from T to S. The time to perform all updates is O(m) since the arc (i,j) is only involved in update(i). FindMin Time: To find the minimum (in a straightforward approach) involves scanning d(j) for each j ∈ T. Initially T has n elements. So the number of scans is n + n-1 + n-2 + … + 1 = O(n2). O(n2) time in total. This is the best possible only if the network is dense, that is m is about n2. We can do better if the network is sparse. 13Application 19.19. Dynamic Lot Sizing K periods of demand for a product. The demand is djin period j. Assume that dj> 0 for j = 1 to K. Cost of producing pj units in period j: aj + bjpj hj : unit cost of carrying inventory from period j Question: what is the minimum cost way of meeting demand? Tradeoff: more production per period leads to reduced production costs but higher inventory costs. 14Application 19.19. Dynamic Lot Sizing (1) 1 2 3 4 K-1 K 0 D -d1 -d2 -d3 -d4 -dK-dK-1 Flow on arc (0, j): amount produced in period j Flow on arc (j, j+1): amount carried in inventory from period j Lemma: There is production in period j or there is inventory carried over from period j-1, but not both. 15Lemma: There is production in period j or there is inventory carried over from period j-1, but not both. Suppose now that there is inventory from period j-1 and production in period j. Let period i be the last period in which there was production prior to period j, e.g., j = 7 and i = 4. Claim: There is inventory stored in periods i, i+1, …, j-1 4 5 6 7 K-1 K 0 D -d4 -d5 -d6 -d7 -dK 16-dK-14 5 6 7 K-1 K 0 D -d4 -d5 -d6 -d7 -dK-dK-1 Thus there is a cycle C with positive flow. C = 0-4-5-6-7-0. Let x07 be the flow in (0,7). The cost of sending D units of flow around C is linear (ignoring the fixed charge for production). Let Q = b4 + h4 + h5 + h6 – b7. If Q < 0, then the solution can be improved by sending a unit of flow around …

View Full Document