- Given n cities and connecting flight details with cost and date .
Flight:
{Source - A | Dest - B | Date -> 1| cost-> 40,
Source - B | Dest - C | Date -> 2| cost->120,
Source - A | Dest - D | Date -> 3 | cost-> 80,
Source - D | Dest - k | Date -> 4 | cost-> 70,
Source - K | Dest - Z | Date ->5 | cost-> 55,
Source - K | Dest - A | Date -> 6 | cost-> 90}
- Given Hotel cost per night for each cities.
{city -> A | cost-> 20 Per/night,
city -> B | cost-> 30 Per/night
city -> C | cost-> 10 Per/night
city -> D | cost-> 35 Per/night
city -> K | cost-> 55 Per/night
city -> Z | cost-> 60 Per/night}
user will provide 3 input:
- Source from where journey will start
- #of days of trip.
- Budget of Trip.
We need to find the longest possible journey path user can make within the Budget of Trip and #of days for trip. and person need to come back to source withing same budget.
Complete journey cost is : cost of flight + hotel cost to stay in the ctiy
public SutibleJourneyPath planTrip(String source, int noOfDays, int maxbudget){
}
Find path with minimum cost and maximum length given a maximum cost
I'm searching for an algorithm to find a path between two nodes with minimum cost and maximum length given a maximum cost in an undirected weighted complete graph. Weights are non negative.
Could someone point me to a known algorithm for better handling of this problem?
To clarify: ideally the algorithm should search for the path of minimum cost, but is allowed to add cost if this means visiting more nodes. It should end when it concludes that it's impossible to reach more than n nodes without crossing the cost limit and it's impossible to reach n nodes with less cost.
Update
Example of a graph. We have to go from A to B. Cost limit is set to 5:
graph This path (in red) is ok, but the algorithm should continue searching for better solutions
enter image description here
This is better because although the cost is increased to 4, it contains 1 more node
enter image description here
Here the path contains 3 nodes so it's a lot better than before and the cost is an acceptable 5
enter image description here
Finally this solution is even better because the path also contains 3 nodes but with cost 4, with is less than before.
enter image description here
Hope images explain better than text