# Graph theory: path of X cost between two nodes

I'm looking for a way to, in any given connected, undirected graph, calculate a path between any two nodes with a cost as close as possible to a given value.

The example is in this image (sorry, I can't embed images yet): A simple graph

Note: the visual length of each edge doesn't exactly match the cost of the edge.

For example, say I want to find a path between A & C of cost as close as possible to 30. I don't want to find the shortest path (A->L->F->E->C) of cost 19, but the path with cost of 31 (A->B->C).

Anybody know of any efficient algorithms to do this?

I've also asked this question on StackOverflow, here.

Also, I am unsure of the tagging applicable to this question. I've attempted to make 'routing' and 'pathfinding' however they don't seem to exist.

In the special case of "there are $n$ vertices, all edges have cost $1$, and the value you want to approximate is $n-1$" this is just the question of whether the graph $G$ contains a Hamiltonian path between two vertices. So you're out of luck having a general efficient algorithm.
It's possible that the best thing to do is the naive approach of trying all paths and pruning when they get too long. (That is, once you've found a path between the two vertices of length $y>x$, where $x$ is the target value, you can start pruning paths going anywhere that have a total length of $y$ or more.)
• Yeah, that was similar to my thinking: repeatedly remove the edges in the shortest path until you have a path of length x. Only issue there is disconnecting the graph or missing some potentially better suited paths that travel along a section of one of the removed shortest paths. – Jordan MacLachlan Apr 19 '18 at 6:01