# Finding path with specific length in weighted graph

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.

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

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$$.