1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jordan MacLachlan Apr 19 '18 at 6:01
  • $\begingroup$ I don't mean actually removing edges. I mean just keeping a list of all the paths, extending each one by all possible edges, but discarding a path once it gets too big. $\endgroup$ – Misha Lavrov Apr 19 '18 at 6:06
  • $\begingroup$ Gotcha - full blown flood search with stopping conditions. Issue is, I want to be able to run the algorithm very regularly so it needs to be efficient. $\endgroup$ – Jordan MacLachlan Apr 19 '18 at 6:11
  • $\begingroup$ Since it has finding a Hamiltonian path as a special case, an efficient algorithm is worth a million dollars :P $\endgroup$ – Misha Lavrov Apr 19 '18 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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