MIT 15 082J - Dijkstra’s Algorithm for the Shortest Path Problem

Unformatted text preview:

15.082J & 6.855J & ESD.78J September 23, 2010Single source shortest path problemOverview of today’s lectureA Key Step in Shortest Path AlgorithmsUpdate(7)On UpdatesDijkstra’s AlgorithmSlide 8Invariants for Dijkstra’s AlgorithmVerifying invariants when S = { 1 }Verifying invariants InductivelyA comment on invariantsComplexity Analysis of Dijkstra’s AlgorithmMental BreakSlide 15Application 19.19. Dynamic Lot SizingApplication 19.19. Dynamic Lot Sizing (1)Slide 18Slide 19Slide 20Slide 21NextPriority QueuesStoring B in a complete binary tree.Slide 25Slide 26Slide 27Finding the minimum elementDeleting or inserting or changing an elementComplexity Analysis using Priority QueuesComments on priority queuesSummarySlide 3315.082J & 6.855J & ESD.78JSeptember 23, 2010Dijkstra’s Algorithm for the Shortest Path Problem2Single source shortest path problemFind the shortest path from a source node to each other node. 123456242 1342 321∞∞∞∞∞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 nodes3Overview 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)4A 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 1 to node i.Procedure Update(i)for each (i,j)∈A(i) doif 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 label correcting algorithm5Update(7)1 8 2 71 3 20 1 4 69532131198d(7) = 6 at some point in the algorithm, because of the path 1-8-2-7Suppose 7 is incident to nodes 9, 5, 3, with temporary distance labels as shown.We now perform Update(7). 87no change6On UpdatesNote: distance labels cannot increase in an update step. They can decrease.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. 1 8 2 71 3 20 1 4 6953213119887no change7Dijkstra’s AlgorithmLet 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.8Dijkstra’s AlgorithmS : = {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 Animated9Invariants for Dijkstra’s Algorithm1. 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.10Verifying invariants when S = { 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}.∪123456242 1342 321024∞∞∞Consider S = { 1 } and after update(1)11Verifying invariants Inductively12 46242 1342 a2032364∞56Any 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). Assume that the invariants are true before a node selectiond(5) = min {d(j) : j T}. ∈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).12A comment on invariantsIt 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.13Complexity 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.Norris Costillo painted the smallest oil on canvas painting in the world. Approximately how large was it?It was 3/8 inches long and a 1/4 inch wide. What ability was Leonardo Da Vinci most proud of?He could bend iron with his bare hands.Alexander Graham Bell never telephoned his wife or mother. He had a good reason. What was it?They were both deaf.Mental BreakWho is buried in Voltaire’s Tomb?Nobody. His body was found missing when the tomb was opened in 1864.True or false. Albert Einstein was once offered the Presidency of Israel.True. In 1952.What unusual anatomic feature did Hitler and Napoleon share? They both had only one testicle.Mental Break16Application 19.19. Dynamic Lot SizingK periods of demand for a product. The demand is dj in 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.17Application 19.19. Dynamic Lot Sizing (1)1 2 3 4 K-1 K0D-d1-d2-d3-d4-dK-1-dKFlow on arc (0, j): amount produced in period jFlow on arc (j, j+1): amount carried in inventory from period jLemma: There is production in period j or there is inventory carried over from period j-1, but not both.18Lemma: There


View Full Document

MIT 15 082J - Dijkstra’s Algorithm for the Shortest Path Problem

Download Dijkstra’s Algorithm for the Shortest Path Problem
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Dijkstra’s Algorithm for the Shortest Path Problem and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Dijkstra’s Algorithm for the Shortest Path Problem 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?