# Single pair shortest path algorithm with time a constraint

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 :)

• 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? – BlueRaja - Danny Pflughoeft Oct 5 '17 at 19:53
• 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? – D.W. Oct 5 '17 at 19:55
• @D.W. edited the question with exact definitions – ironstein Oct 5 '17 at 20:51
• @BlueRaja-DannyPflughoeft edited the question with exact definitions – ironstein Oct 5 '17 at 20:52

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.