5
$\begingroup$

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 $A\to 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 $A\to C\to D\to E\to B$).

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It might be worth noting that the general idea of "copy the graph $k$ times" would give you a runtime of $O(km + kn \log kn)$ for an $m$-edge, $n$-node graph, which is a pseudopolynomial-time algorithm that happens to be strongly polynomial time in the case where $k \le n$. $\endgroup$ – templatetypedef Nov 17 '16 at 1:07
-2
$\begingroup$

I will describe an algorithm that will solve any hamiltonian path problem in any number of dimensions in polynomial time. Due to triangle inequality we know the solution to a hamiltonian path problem will be a perimeter( on the euclidian plane). The brute force practice of finding every possible path can be pared in to polynomial time by only finding sufficiently short possible perimeters. The data sets of distances between points(in any number of dimensions) will be sorted. The three shortest distances will form a triangle. For each side of this triangle the next shortest point to include will be found by finding the closest point to include along each side. Using the sorted tables the computer will find the next closest non-included point and then sum with the path the other point on the perimeter. These possible inclusions can be stored in a sorted list so that as every new point is added only two new line segments will need to find their next closest points. This continues until the first possible solution is found. This solution becomes the goal post and will be no longer than 200% of the actual solution. From my initial thought errors induced would have to be under 15% of the next closest point inclusions. The algorithm would then be able to go thru the data and construct new possible solutions by including the next shortest points up to 15% longer than the first path. Recursive addition will then construct a new possible perimeter until it becomes the new goalpost or passes it.

$\endgroup$
  • $\begingroup$ Quite strong claims. Can you support them with a proof? How does it answer the question? $\endgroup$ – Evil Nov 19 '16 at 11:24
  • $\begingroup$ The original question was an algorithm to find an n-edge path. From my quick search through available papers on the subject this method doesn't exist, as j_random_hacker stated, and is widely believed to not to exist. Possible perimeters do not grow factorially, only possible paths. Even with out the paring this will run in polynomial time, but why would anybody stop there. I guess it's time to write a paper. $\endgroup$ – Steven Ettinger Nov 19 '16 at 17:44

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.