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?
Path in directed, weighted, cyclic graph with total distance closest to D?
graph theory;graphs;optimization;weighted graphs;hamiltonian path
As far as I can tell, the first bibliographical reference I'm aware of within the context of heuristic search is Lukas  Kuhn, Tim  Schmidt,  Bob  Price, Johan de Kleer, Rong Zhou, and Minh Do. Heuristic search for target-value path  problem.   In The First  International Symposium onSearch Techniques in Artificial Intelligence and Robotics, 2008. Since then, this problem is known as Target-Value Search, or TVS for short.Similar ideas were then continued in another paper published the next year at SoCS (the Symposium on Combinatorial Search) but employing a depth-first search instead: Tim  Schmidt,  Lukas  Kuhn,  Bob  Price,  Johan de Kleer, and Rong Zhou.  A depth-first approach to target-value search. In Symposium on Combinatorial Search (SOCS-09), 2009.Interestingly, the algorithms described in these works solve the problem for graphs with arbitrary edge costs. However, they only perform experiments with tiny graphs (e.g., a few tens of nodes). Another team of researchers proposed a different algorithm for the case of unitary edge costs (ie., where all edge costs are restricted to be the same): Carlos Linares Lpez, Roni Stern, Ariel Felner: Target-Value Search Revisited. IJCAI 2013: 601-607. They performed experiments with much larger graphs (ie., hundreds of thousands of nodes).In this paper, the authors identified three different variants of the TVS. They originally addressed the case where vertices can be repeated but edges cannot be traversed twice.That's not the case you are interested in! The specific case of simple paths was addressed in a short communication published in SoCS in 2014: Carlos Linares Lpez, Roni Stern, Ariel Felner: Solving the Target-Value Search Problem. SOCS 2014. You will find in this paper the same reduction mentioned by D.W. from the SUBSET SUM PROBLEM to prove NP-hardness. As mentioned above, however, the last two works are specific to the case where all edge costs are equal to one. All the algorithms mentioned in this response compute optimal solutions and I'm not aware of any approximation algorithms for solving this problem.Hope this helps,