2
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ironstein Oct 6 '17 at 1:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.