I am currently studying shortest path problems and for one of the assignment problems, I just can't figure out. The problem is below:
A guy wants to rent out his yacht from May 1 to September 1. He places an ad in the newspaper and gets 10 offers with different time periods (ex: July 1 to Aug 1) and different Dollar amounts.
My assignment is "simple": graph it as a "shortest path problem". What I don't understand is if the guy wants to maximize his revenue, shouldn't this be a widest path problem instead? Why shortest path?
Also, is there any sense in using dummy nodes to signify that during time period xxx-yyy, there is no offer to choose from? To illustrate with an example, let's say he has an offer from July 1st to July 15th; no offers from the 15th to the 30th, and then an offer from the 30th to August 15. Should I put a "dummy" node from the 15 to 30?
Thanks so much for your help.
Make a graph with 12 nodes, 1 for each lease offer, a start node and an end node. Draw a directed edge from a given node to another node if you can take the lease at the new node after you finish the one at the given node. The edges should be weighted with the negative of the monetary value of the lease. Then the path across the graph from the start to end node with minimum cost(shortest path) is a feasible set of leases that generates the most revenue.