Single pair shortest path algorithm with time a constraint

Question

I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional constraint "the total time should not exceed T time units", then the problem becomes much harder.

More formally:

The input consists of a set of n cities and m roads between pairs of cities. There can be multiple roads between a pair of cities $(i, j)$. For each road, you are given its departure city $x_i,ドル its destination city $y_i,ドル its duration $d,ドル and its cost $c$. The objective is to find the cheapest path between a pair of cities $(a, b)$ such that the cost is minimized while keeping the duration less than the maximum duration $T$.

I tried thinking on the lines of Dijkstra's and modifying the graph so that it is in some way possible to run a shortest path algorithm on it, but there seems to be no trivial way of doing this. Simple solutions like (follow a greedy strategy until you exceed the time limit, and then move on to the next element in the priority queue) don't seem to work because the use of a priority queue in the Dijkstra's algorithm and DEQUEUING the minimum element from the priority queue behave like destructive operations. There is a need to backtrack (of sorts) but the shortest path algorithms visit each node in the graph only once.

I've tried thinking about other simpler approaches using the Bellman-Ford algorithm, but the time complexity of the algorithm I turned out writing depended on $T$ (which is not very desirable).

I spent almost 2 days on this and every solution I try either seems to not work, or runs in exponential time. Is this problem NP hard or are there polynomial time solutions possible?

P.S. I am not looking for a practical implementation of this problem, just an algorithm that can solve this problem in polynomial time. Although any thoughts about how to efficiently implement this would be more than welcome :)

• BlueRaja - Danny Pflughoeft: What does "the total time should not exceed T time units" mean? Do distances on the graph have a time associated with them? Or do you mean the algorithm itself should be time-bounded?
• D.W.: Please edit the question to clarify the problem. What are the inputs? Do edges have both a distance and a time associated with them? Are the times integers? Are you looking for a practical solution or for its theoretical complexity? If you want something practical, is T expected to be huge or to be not too big? What's the context where you ran into this problem? Is it an exercise? Can you cite the source for it?
• ironstein: @D.W. edited the question with exact definitions
• ironstein: @BlueRaja-DannyPflughoeft edited the question with exact definitions

Answer 1

Your problem is NP-hard: The partition problem reduces to it as follows:

Let $ S = \{s_0, ... , s_{n-1} \} $ be a multiset of non-negative integers.

Construct cities $ \{ c_0, ... , c_n \} ,ドル with each city $ c_i $ having 2 roads to $ c_{i+1} ,ドル one with duration $ 0 $ and cost $ s_i ,ドル the other with duration $ s_i $ and cost $ 0 $.

Then find the minimum-distance path from $ c_0 $ to $ c_n $ with total duration at most $ \frac 1 2 \sum S $. This path has equal cost and duration iff $ S $ can be partitioned into subsets of equal sum.

• ironstein: Hi, thanks for the answer. Is there any way we can make this problem not NP-hard by adding additional constraints. I mean, off the top of my head, something like we can introduce departure times for each of the flights. Would that make any difference?