Given a graph as in Fig. 1, we are interested in finding the shortest paths from...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Given a graph as in Fig. 1, we are interested in finding the shortest paths from the source a to all other vertices using the Dijkstra's algorithm and a min-heap as a priority queue. Note that a min-heap is the same as a max-heap, except that the key stored at a parent node is required to be smaller than or equal to the keys stored at its two child nodes. In the context of the Dijkstra's algorithm, a node in the min-heap tree has the format v(pv, dv), where d, is the length of the current shortest path from the source to v and p, is the second to last node along that part (right before v). For example, b(a, 4) is one such node. We treat d, as the key of Node u in the heap, where uela,b,c,d,e, f,g,h}. Source: 3 C 6 h Figure 1: An input graph for the Dijkstra's algorithm. Edge weights are given as integers next to the edges. For example, the weight of the edge (a, b) is 4. a) [1 mark] The min-heap after a(a,0) is removed is given in Fig. 2. The next node to be removed from the heap is b(a, 4). Draw the heap after b(a, 4) has been removed and the heap has been heapified (fixed), assuming that co2oo. No intermediate steps are required. c(a, 8) b(a, 4) d(a, 6) e(-,∞0) f(-∞) g(,00) h(-,∞0) Figure 2: The min-heap (priority queue) after a(a,0) has been removed. b) [2 marks] Draw the heap(s) after the neighbours of b have been updated and the heap has been heapified (see the pseudocode in the lecture Slide 30, Week 9). If there are multiple updates then draw multiple heaps, each of which is obtained after one update. Note that neighbours are updated in the alphabetical order, e.g., 6 must be updated before c. No intermediate steps are required. Follow the dis- cussion on Ed Forum for how to update a node in a heap. 1 a(a,0) 2 a(a,0), bla,4) 3 34 4 10 5 6 S: vertices whose shortest paths have been known 7 8 c) [5 marks] Complete Table 1 with correct answers. You are required to follow strictly the steps in the Dijkstra's algorithm taught in the lecture of Week 9. d) [2 marks] Fill Table 2 with the shortest paths AND the corresponding distances from a to ALL other vertices in the format a →??→v|dy, for instance, a - b 4. a a-a b a → b с d 2485 e f g Priority queue of remaining vertices b(a, 4), c(a, 8), d(a, 6), e(-,co), f(-,co), g(-, oo),h(-,00) Table 1: Complete this table for Part c). h Shortest Paths Table 2: Complete this table for Part d). Distances 0 4 Given a graph as in Fig. 1, we are interested in finding the shortest paths from the source a to all other vertices using the Dijkstra's algorithm and a min-heap as a priority queue. Note that a min-heap is the same as a max-heap, except that the key stored at a parent node is required to be smaller than or equal to the keys stored at its two child nodes. In the context of the Dijkstra's algorithm, a node in the min-heap tree has the format v(pv, dv), where d, is the length of the current shortest path from the source to v and p, is the second to last node along that part (right before v). For example, b(a, 4) is one such node. We treat d, as the key of Node u in the heap, where uela,b,c,d,e, f,g,h}. Source: 3 C 6 h Figure 1: An input graph for the Dijkstra's algorithm. Edge weights are given as integers next to the edges. For example, the weight of the edge (a, b) is 4. a) [1 mark] The min-heap after a(a,0) is removed is given in Fig. 2. The next node to be removed from the heap is b(a, 4). Draw the heap after b(a, 4) has been removed and the heap has been heapified (fixed), assuming that co2oo. No intermediate steps are required. c(a, 8) b(a, 4) d(a, 6) e(-,∞0) f(-∞) g(,00) h(-,∞0) Figure 2: The min-heap (priority queue) after a(a,0) has been removed. b) [2 marks] Draw the heap(s) after the neighbours of b have been updated and the heap has been heapified (see the pseudocode in the lecture Slide 30, Week 9). If there are multiple updates then draw multiple heaps, each of which is obtained after one update. Note that neighbours are updated in the alphabetical order, e.g., 6 must be updated before c. No intermediate steps are required. Follow the dis- cussion on Ed Forum for how to update a node in a heap. 1 a(a,0) 2 a(a,0), bla,4) 3 34 4 10 5 6 S: vertices whose shortest paths have been known 7 8 c) [5 marks] Complete Table 1 with correct answers. You are required to follow strictly the steps in the Dijkstra's algorithm taught in the lecture of Week 9. d) [2 marks] Fill Table 2 with the shortest paths AND the corresponding distances from a to ALL other vertices in the format a →??→v|dy, for instance, a - b 4. a a-a b a → b с d 2485 e f g Priority queue of remaining vertices b(a, 4), c(a, 8), d(a, 6), e(-,co), f(-,co), g(-, oo),h(-,00) Table 1: Complete this table for Part c). h Shortest Paths Table 2: Complete this table for Part d). Distances 0 4
Expert Answer:
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these computer network questions
-
If preferred stock sold for $99 a share and $2.95 dividends were paid annually, what would be the required rate of return? show all steps and work
-
Determine the force in each member of the space truss in E9.3.27 if the magnitudes of F and F are 8 kip and 4 kip, respectively. State whether each member is in tension or compression. 2 ft F2 2 ft...
-
A scaling algorithm solves a problem by initially considering only the highest-order bit of each relevant input value (such as an edge weight). It then refines the initial solution by looking at the...
-
Ag Bio Tech (ABT) was organized on January 1, 2013, by four friends. Each organizer invested $10,000 in the company and, in turn, was issued 8,000 shares of common stock. To date, they are the only...
-
Discuss the purpose of a layer of copper or aluminum on the bottoms of stainless steel cookware?
-
Alou Equipment Repair has a September 30 year end. The company adjusts and closes its accounts on an annual basis. On August 31, 2017, the account balances of Alou Equipment Repair were as follows:...
-
Voluntary accounting policy changes are said to be unintended signals about the financial health and future prospects of a firm from management to a firms shareholders. Discuss how and why you would...
-
As noted in this chapter, because of global competition, companies have become increasingly focused on reducing costs. To reduce costs and remain competitive, many companies are turning to...
-
Summit Corporation manufactures machines for the apparel industry. The production manager and cost analyst reviewed the accounts for the previous quarter and have provided an estimated breakdown of...
-
1. Bare cost and total cost (incl. O&P) of formwork for spread footings (20 pts, specify which lines (or index) in RSMeans data are used) 2. Bare cost and total cost of reinforcement for spread...
-
The following selected transactions are taken from the Aliceville Company books for 2014 1. On March 1, 2014, he borrowed $48,000 in cash from the local bank.The note carried an interest rate of 8...
-
Describe three major steps in the process of developing a relevant communication strategy within a named societal sector
-
Discuss the role of law in civil ? Discuss Statute law with a suitable example. Need explanation in more than two hundred and also explain reason for the answer IN TEXT FORM Please provide correct...
-
An Australian firm has net receivables of 200,000 SGD in three-months' time as compensation for work undertaken. Current spot rate is AUD/SGD 0.9819/0.9855 Interest rates in Singapore are currently...
-
DigiCom is a new company trying to take market share away from Apple's IPodin the MP3 player market. They are offering the 8gb Lame for $50 each, and the 16gb Lame Plus for $100. Their variable costs...
-
c) Your boss believes that the correct expected return for Telestor equals 0,11. Show how you can put together a portfolio of Oljelund, H20Kraft, Telestor in a way that earns you a risk-free...
-
When Silicon Valley Bank was flooded with billions of new deposits in 2021, it chose to invest a significant portion of them in long-dated treasury and agency notes. What were the other options...
-
Chris Zulliger was a chef at the Plaza Restaurant in the Snowbird Ski Resort in Utah. The restaurant is located at the base of a mountain. As a chef for the Plaza, Zulliger was instructed by his...
-
Give an inductive definition for an n-tuple by extending the set-theoretic definition for an ordered pair.
-
Show that for all a > 0 and all k such that 0 k-1 k a' < ( + 1)" b(k;n,a/( + 1)) -k( + 1) i=0
-
Show that if f (n) = (n log b a lg k n), where k 0, then the master recurrence has solution T (n) = (n log b a lg k + 1 n). For simplicity, confine your analysis to exact powers of b.
-
A monopolist produces at an output where the price is _________ than its marginal cost, so the value to society from the last unit produced is _________ than its marginal cost.
-
An argument against monopoly is that a lack of competition tends to retard _________ advance; but, in fact, many near monopolists are important innovators.
-
The goal of government regulation as an alternative approach to dealing with monopolies is to achieve the efficiency of large-scale production without permitting the _________ monopoly prices and...
Study smarter with the SolutionInn App