Reputation: 4868
I want to solve a variation of shortest path algorithm. I can't figure out how to deal with additional constraints.
Few cities
(<=50)
are given along with two(N * N)
matrices denoting travel time between cities and toll between cities. Now given a timet
(<10000)
, we have to choose a path to reach from city0
to cityN-1
such that toll cost is minimum and we complete travel within given timet
.
I know that with only one parameter such as only time, we can use shortest path algorithm such as Bellman–Ford algorithm
or Dijkstra's algorithm
. But how to modify it so to include two constraints? How can we formulate Dynamic Programming solution for the problem?
I am trying to solve it with DP + complete search. Am I in right direction, or are there better algorithms than these approach?
Upvotes: 4
Views: 1764
Reputation: 11294
It is possible to use Dijkstra for this problem, first you need to create a graph of state, with each state represents the city and time left. So between each state (city A, time t ) and state (city B , time t1), there can only be an edge if you can move from city A to city B with the given time is (t1 - t). And the value for each edges will be the toll. Solving this using standard Dijkstra is simple.
Upvotes: 2