Path in directed, weighted, cyclic graph with total distance closest to D? Input: Directed, weighted, cyclic graph G. Two distinct vertices in that graph, A and B, where there exists a path from A to B. A distance d.

Output: A path between A and B with distance closest to d. The path need not be a simple path - it can contain repeated edges and vertices.

Which algorithms exist to solve this problem? I'm looking for an optimal solution, but I'm also interested to see if there are any approximation algorithms as well. Efficiency is not a huge concern - I just want to get an idea of the algorithms available.



Bonus question: are there any algorithms to compute a path from A to B that visits every node at least once, while finding the distance closest to d?
The problem is NP-hard, by reduction from subset sum (given weights $w_1,\dots,w_n$, take a graph with $n$ vertices and two edges from vertex $i$ to vertex $i+1$, one of weight zero and one of weight $w_i$).

One algorithm is to simply enumerate all paths up to a certain length (say, up to length $2d$, if all edge weights are non-negative).  This can be done by enumerating all paths of length $i$; then enumerating all paths of length $i$ by concatenating any path of length $i$ followed by any edge out of the final vertex of that path; and so on, for $i=1,2,3,\dots$  Of course, the algorithm takes exponential time, but it is an algorithm.