CODEWITHSUNDEEP
algorithmdynamic-programmingdijkstrashortest-path
coder hacker
coder hacker

Reputation: 4868

Shortest Path Algorithm with some Restrictions

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 time t (<10000), we have to choose a path to reach from city 0 to city N-1 such that toll cost is minimum and we complete travel within given time t.

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

Answers (1)

Pham Trung
Pham Trung

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

Related Questions