Suppose that you are searching for an airline flight. You will be interested in the price...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Suppose that you are searching for an airline flight. You will be interested in the price of the flight, but you will probably also be interested in the amount of time that the flight(s) will take. This program is based on that problem. You will be given a directed graph where each edge has a cost and a duration. Your job will be to find the shortest duration path that doesn't go over a given total cost. The graph will be given as follows. The number of vertices and edges will be on the first line, followed by one edge per line. Each edge will have the two vertices, the cost and the duration, all of which will be positive integers. Note that in this graph there may be multiple edges between any two vertices. Your program should take four command line arguments: the name of the file containing the graph, the start vertex, the end vertex, and the maximum total cost. The output of the program is a single integer, the duration of the cheapest path from the start vertex to the end vertex with total cost less than the limit. If no path exists with cost less than the limit, output a 0. No other output should appear. Hint: for this program, you will want to modify the Bellman-Ford algorithm. Instead of a single weight for each vertex of the graph, you will need to maintain an ordered list based on cost. Example input graph: 57 01 30 100 04 50 125 12 250 50 12 50 150 42 40 100 23 60 90 43 150 125 Executing project5 graph.txt 0 3 200 Should output 250 Executing project5 graph.txt 0 3 140 Should output 340 Executing project5 graph.txt 0 3 139 Should output 0 Suppose that you are searching for an airline flight. You will be interested in the price of the flight, but you will probably also be interested in the amount of time that the flight(s) will take. This program is based on that problem. You will be given a directed graph where each edge has a cost and a duration. Your job will be to find the shortest duration path that doesn't go over a given total cost. The graph will be given as follows. The number of vertices and edges will be on the first line, followed by one edge per line. Each edge will have the two vertices, the cost and the duration, all of which will be positive integers. Note that in this graph there may be multiple edges between any two vertices. Your program should take four command line arguments: the name of the file containing the graph, the start vertex, the end vertex, and the maximum total cost. The output of the program is a single integer, the duration of the cheapest path from the start vertex to the end vertex with total cost less than the limit. If no path exists with cost less than the limit, output a 0. No other output should appear. Hint: for this program, you will want to modify the Bellman-Ford algorithm. Instead of a single weight for each vertex of the graph, you will need to maintain an ordered list based on cost. Example input graph: 57 01 30 100 04 50 125 12 250 50 12 50 150 42 40 100 23 60 90 43 150 125 Executing project5 graph.txt 0 3 200 Should output 250 Executing project5 graph.txt 0 3 140 Should output 340 Executing project5 graph.txt 0 3 139 Should output 0
Expert Answer:
Answer rating: 100% (QA)
Solution code include include include include using namespace std struct Edge int src dest costduration a structure to represent a connected directed ... View the full answer
Related Book For
Basic Business Statistics Concepts and Applications
ISBN: 978-0132168380
12th edition
Authors: Mark L. Berenson, David M. Levine, Timothy C. Krehbiel
Posted Date:
Students also viewed these programming questions
-
Using multiple department factory overhead instead of a single plantwide factory overhead rate: a. results in more accurate product costs b. is simpler and less expensive to compute than a plantwide...
-
A new weight loss program claims that participants will lose an average of more than 10 lbs after completing it. The following table shows the weights of eight individuals before and after the...
-
A graph is k-colorable if each vertex can be given one of k colors, and no edge connects identically colored vertices. Give a linear-time algorithm to test a graph for two-colorability. Assume graphs...
-
find the steady state expression for vo in the circuit fig 9.32 if ig = 500cos2000tmA 3) 9.32 Find the steady-state expression for u,, in the circuit of Fig. P9.32 if i = 500 cos 2000 mA. Figure...
-
Paul Corporation reports the following inventory information: Assuming Paul uses a perpetual inventory system and the direct method, prepare the journal entry' to record the reductions to market....
-
If the bearings at \(A\) and \(B\) exert only vertical reactions on the shaft, determine the slope at \(A\) and the maximum deflection of the shaft. \(E I\) is constant. 50 lb-ft 50 lb-ft A B 2 ft 4...
-
It is desired to find the value f0.99 for an F10,5 distribution. Use Table A.5 and the F5,10 distribution to find this value. Table A.5 Critical Values for the F Distribution Area Denominator Degrees...
-
In 2010, Lee Ann Adams and some college friends organized The Candy Jar, a gourmet candy company. In 2010, The Candy Jar issued 150,000 of the 300,000 authorized shares of common stock, par value...
-
2 7 The bank made an EFT payment of a telephone bill of $ 5 , 0 0 0 . How would this information be included on the bank reconciliation?
-
1. Look at the list of accounts (in no particular order) of Geewhiz Productions at 30 November 2015 and decide which ones are income statement accounts. 2. Calculate net profit based on your answer...
-
Explain (in detail) with the help of suitable examples the following digital forensics concepts/terms. Explain file fragmentation problem with respect to FAT and NTFS Importance of booting process in...
-
The skier departs the horizontal ski run with a speed of v=110 km/h, soaring into the air. Upon landing, the slope he/she encounters forms a 45 angle with the horizontal plane. Calculate the skier's...
-
A drone has a speedometer and a compass as part of its instrumentation. The speedometer tells you the speed of the drone and the compass tells you the direction the drone moves. While the drone is...
-
My industry is NAIC code is 541213 Tax Preparation in Chicago, Illinois Section A: Business Concept: (50 points) Please describe the purpose of the selected company, including a detailed description...
-
A swimmer competes in a 100 m race. He completes the length of the 50.0 m swimming pool in 39.5 s, and makes the return lap in 42.0 s. (Assume that the swimmer moves in a straight line through his...
-
1. Suppose you measure three independent variables as x = 10 2, y = 7 1, = 40 3, and use these values to compute = + 2/ + sin (4) What should be your answer for and its uncertainty? 2. The Type K...
-
Explain the difference between culpable and innocent absenteeism. Give an example of each. write new answer with well description.
-
Diamond Walker sells homemade knit scarves for $25 each at local craft shows. Her contribution margin ratio is 60%. Currently, the craft show entrance fees cost Diamond $1,500 per year. The craft...
-
A recent survey of college freshmen investigated the amount of involvement their parents have with decisions concerning their education. When asked about the decision to go to college, 84% said their...
-
Why does the sampling distribution of the mean follow a normal distribution for a large enough sample size, even though the population may not be normally distributed? Discuss.
-
In Problem 14.8 on page 584, you used land area of a property and age of a house to predict appraised value (stored in GlenCove). Use the results from that problem. a. Construct a 95% confidence...
-
Examine the Dollarama statement of cash flows. Suppose Dollarama's operating activities used, rather than provided, cash. Identify three things under the indirect method that could cause operating...
-
Which of the following is a misappropriation of assets? a. Classifying inventory held for resale as supplies. b. Investing cash and earning a 3 percent rate of return as opposed to paying off a loan...
-
Canada Wide Transportation (CWT) began 2020 with accounts receivable, inventory, and prepaid expenses totalling \(\$ 65,000\). At the end of the year, CWT had a total of \(\$ 78,000\) for these...
Study smarter with the SolutionInn App