Shortest Path Algorithm with some Restrictions

4
votes

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?

1
algorithmdynamic-programmingdijkstrashortest-path
You can try this, create copies of the graph that represent time and toll between the cities .. then solve these graphs together, while in step i you will be able to minimize though all of these constraints – Khaled.K
It seems ok to me, so your dp state is [time left][city]? The time left condition will help your program avoid the infinite loop, should be fine! – Pham Trung
@PhamTrung Yes i thought about same approach, but was not sure if it was the best – coder hacker
I had that one time in an IA exam and the correct answer was to set a heuristic to combine both constraints. It might not be optimal thought. Take a look at the A star algorithm. It might give you an idea – eliasah
Try to google shortest path with time constraint. It will give you a bunch of papers on this subject. The problem is apparently NP hard. – Ali

1 Answers

2
votes

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.