Problem Detail: Is there an efficient algorithm which computes the (possibly approximately) shortest $n$-edge path between two points $A$ and $B$ in a weighted complete graph? Dijkstra won’t work because it will just give the trivial answer of $Ato B$. I’d like to find an $n$-edge path (e.g. for $n=4$, find $C$, $D$ and $E$ which minimize total path length of $Ato Cto Dto Eto B$).
Asked By : genekogan
Answered By : j_random_hacker
If vertices can be visited more than once, then yes: you can create $n+1$ copies of the graph, with each vertex $v$ in the original graph becoming the $n+1$ vertices $v_1, dots, v_{n+1}$ and each edge $uv$ in the original graph becoming the set of edges $u_iv_{i+1}$ for all $1 le i le n$; now run Dijkstra on the resulting graph with start vertex $A_1$ and end vertex $B_{n+1}$. Intuitively, each edge traversed in any path necessarily takes you to the next “level” of the graph. If vertices cannot be visited more than once, then there’s no known poly-time algorithm, since setting setting $n$ to one less than the number of vertices would solve the NP-hard Hamiltonian Path problem. (Although the HP problem technically asks for any path that visits all vertices exactly once, a poly-time algorithm for the simple-paths version of your problem would nevertheless give you a poly-time algorithm for HP: just run it $O(n^2)$ times, one for each possible pair of start and end vertices.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/66116
