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...
-
Winthur Stores began operations on January 1, 2012, and adopted the FIFO method of accounting for its inventory for book and tax purposes. In 2015, it is considering a change to the average- cost...
-
Deb and Jan were partners in the operation of a breakfast/lunch diner. Recent adverse decisions from the County Health Inspector relating to lapses in achieving proper water heating levels in their...
-
For the process \(\mathrm{CO}_{2}(\mathrm{~s}) ightarrow \mathrm{CO}_{2}(\mathrm{~g})\) (a) Both \(H\) and \(S\) are \(+\mathrm{ve}\) (b) Both \(H\) and \(S\) are - ve (c) \(H\) is + ve and \(S\) is...
-
The manager of the Fore and Aft Marina in Problem 16 wants to investigate the possibility of enlarging the docking facility so that two boats can stop for gas and servicing simultaneously. Assume...
-
Rebecca spends $22 each week on a morning Coke and $320 per month on food. (2 pts. each) a) Compute the total cost per year for Rebecca's morning Coke. b) Compute the total cost that Rebecca spends...
-
A. Richard McCarthy (born 2/14/64; Social Security number 100-10-9090) and Christine McCarthy (born 6/1/1966; Social security number 101-21-3434) have a 19-year-old son (born 10/2/99 Social Security...
-
The required return on the stock is {y}%. Given the cash flows in the summary quote, what is the value of the stock? Johnson & Johnson (JNJ) NYSE- Nasdaq Real Time Price. Currency in USD 179.43 +0.79...
-
The Rolling Department of Jabari Steel Company had 3,700 tons in beginning work in process inventory (70% complete) on October 1. During October, 61,700 tons were completed. The ending work in...
-
The management of Mecca Copy, a photocopying center located on University Avenue, has compiled the following data to use in preparing its budgeted balance sheet for next year: Ending Balances ? Cash...
-
Synthesize a statement of Georgia law regarding suppression of evidence, as applicable to the scenario presented below: The attorney you work for in Warner Robins, Georgia, has been hired to defend...
-
Read the following cases and then answer the questions below. Cases: Goddard v. Boston M.R. Co ., 60 N.E. 486 (Mass. 1901) Anjou v. Boston Elevated Ry. Co., 94 N.E. 386 (Mass. 1911) Mascary v. Boston...
-
Sevenways, is a respected upper class residential complex in the so-called leafy surbubs of Nairobi. Kamau, an up-and-coming lawyer in Nairobi, was happy to buy a home for his family in this...
-
What strategy/tactic might marketers use to see which competitors' items are competing against their own items and to identify market segments so they can gauge how well their items are positioned to...
-
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...
-
Determine the slope of the 50 -mm-diameter A-36 steel shaft at the journal bearings at \(A\) and \(B\). The bearings exert only vertical reactions on the shaft. A 500 mm 800 mm 300 N 1200 mm D 300 N...
-
Determine the maximum deflection of the 50 -mm-diameter A-36 steel shaft. 500 mm 800 mm 1200 mm 300 N 300 N 600 N 600 N B
-
Determine the slope at \(A\) of the simply supported beam. EI is constant. B - d --
Python Language Dig Deep Into The Data Mining Process 1st Edition - ISBN: 979-8371092311 - Free Book
Study smarter with the SolutionInn App