I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph.
For example, imagine my phone tells me that I need to walk three miles today. It might be nice if the phone could calculate a few tours of appropriate length, ideally avoiding things like walking up and down the same streets repeatedly.
A previous posting reviewed some algorithms for finding fixed-length cycles in unweighted graphs. However, I'm not aware of anything concerning the edge-weighted case.
A simple algorithm for a road network might work as follows. Assume that I want a cycle of length $x$ that starts and ends at a source vertex $s$. Now use Dijkstra's algorithm to produce a shortest path tree. Next, find the node $v$ in this tree whose distance from $s$ is close to $x/2$. Our solution then involves walking from $s$ to $v$ and then back to $s$ again. While this algorithm is polynomial, the solution is not great as we will end up walking up and down the same streets (so its not really a cycle at all...).
Another option might be to convert a weighted graph into an unweighted one. Assuming all edge-weights are integer, an edge of length $x$ is replaced by a chain of $x-1$ vertices, as the following demonstrates:
We can then apply methods used for the unweighted graphs. An issue with this approach is that it could massively increase the size of the graph. Given that existing approaches for simple graphs can be quite expensive, this doesn't seem like a good idea.
Does anyone have any ideas/thoughts?