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?

---

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.

链接地址: http://www.djcxy.com/p/35232.html

上一篇: 在加权图中找到最短路径

下一篇: 有一些限制的最短路径算法