patternMinor
Path in directed, weighted, cyclic graph with total distance closest to D?
Viewed 0 times
totalpathgraphwithweighteddirecteddistanceclosestcyclic
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#62812, answer score: 2
Revisions (0)
No revisions yet.