1
$\begingroup$

Given a weighted, cyclic, directed graph and two nodes I am looking for a connecting path which total weight comes as near as possible to a specific value which is greater than the shortest path. Example in a real world scenario: Find a route from Washington D.C. to New York City which is 400 miles long, despite the shortest path is ~230 miles. All my considerations so far failed for one of the following reasons:

  • Most routing algorithms like Dijkstra are not working in this case because there is nothing to minimize or maximize (the divergence of given weight to path weight should be minimized, but you need the finished path to calculate it)
  • DFS and BFS can be used to find a path with a specific number of hops (edges), but it doesn't consider weighted edges

EDIT: Cycles are forbidden to avoid the simple solution shortest path + cycles until distance is reached. The algorithm doesn't have to find the optimal solution, a route with length in a given threshold is acceptable.

Improve this question
$\endgroup$
2
  • $\begingroup$ Are loops allowed? I'm assuming it is because you explicitly mention a "cyclic" graph, but I believe that should be clarified. $\endgroup$
    – dkaeae
    Commented Jul 17, 2019 at 13:25
  • $\begingroup$ Good point! Loops are not allowed to prevent the algorithm from doing roundtrips until the desired distance is reached. $\endgroup$
    – Gerrit Schelter
    Commented Jul 17, 2019 at 16:08

1 Answer 1

Reset to default
2
$\begingroup$

Your problem is NP-complete by a reduction from Hamiltonian $st$-path, even with unweighted arcs. Thus, you should not expect a polynomial-time algorithm. I'll sketch a reduction below.

Let $G$ be an instance of Hamiltonian $st$-path with all $m$ arcs having weight 1. Let $G'$ be a graph obtained from $G$ by adding a long directed path of length $C$ starting from $t$ ending at (say) $t'$. Now, if there's an Hamiltonian path from $s$ to $t$, there is also a path from $s$ to $t'$ of length $m$ plus $C$. On the other hand, if there's a path of length $m+C$ from $s$ to $t'$ in $G'$, you can chop off the long path from $t$ to $t'$ to obtain a Hamiltonian $st$-path in $G$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This applies to finding the optimal solution, right? I just edited the question, what about finding a non-optimal route which length is in an acceptable threshold? $\endgroup$
    – Gerrit Schelter
    Commented Jul 18, 2019 at 13:00
  • $\begingroup$ @GerritSchelter This should be highly unlikely as well since Hamiltonian path is very hard to approximate as well - I don't remember the details from the top of my head, but you should find it easily by searching. If you don't insist on formal guarantees (along the lines of "here's a path for you & I guarantee you it is only at most 100 miles longer than the optimum"), heuristics could give you very good solutions in practice. $\endgroup$
    – Juho
    Commented Jul 18, 2019 at 13:42
  • $\begingroup$ Thanks a lot. I already have a working algorithm using heuristics, but it needs a certain length to produce good results. Have t try it again then. $\endgroup$
    – Gerrit Schelter
    Commented Jul 21, 2019 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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