# Solving Hamiltonian graph in a complete directed graph

Suppose I have a complete directed graph G(E,V). If I have acces to a subroutine that calculates the shortest path from s to t (both in V). Can I use this to find an algorithm that determines a Hamiltonian path from s to t in graph G minimizing the sum of the edge costs of the edges used in the path? The edge costs are nonnegative real numbers.

Yes, you can, but the algorithm will still run in exponential time. The shortest path problem is different from the Hamilton path problem: one can be calculated in time $O(|V|\cdot |E|)$, while the other is NP-Complete. So it is easy to compute the $n\times n$ matrix $C$ where $C[u,v]$ is the cost of the shortest path from $u$ to $v$ (easy in the sense that the number of operations required to do this is bounded by a polynomial in $|V|$, namely $|V|^5$). However, it is not easy to do this if you add the requirement that the path not only be the shortest, but also that it visits all the other nodes first. These costs don't allow you to compute a Hamilton path.
For example, one may naively start with the shortest path from $s$ to $t$. But this path may not visit all edges. So we demand that the path visit node $u$, too, so we might simply concatenate the shortest paths $s-u-t$. But this may not be the shortest path that visits all these nodes; maybe it's $s-t-u$, or $u-t-s$; there are $3!=6$ possibilities to choose from. But none of these paths necessarily visit all the nodes, either, so you add another node $v$, and $\ldots$ and then you have $n!$ sequences to choose from, and you are not better off than the brute force algorithm.
In fact, even if the edge weights are $0,1$, determining whether a Hamilton path of weight at least $k$ exists is NP-Complete. Why is this problem so difficult? Nobody knows for sure! We will know why when we settle $P\overset{?}{=}NP$, but until then, we can say that it looks like brute force enumeration is close to the optimal algorithm.
• @Blackjaguar Suppose it did. Then you algorithm with a shortest path oracle runs in $n^k$ for some $k\in \mathbb{N}$ on graphs with $n$ nodes. But in reality, the shortest path algorithm runs in at most $n^3$ time, so in reality your algorithm would run in $n^{k+3}$ time. But we had assumed that in reality, your algorithm was exponential! We have a contradiction. In general composing polynomials leaves you only with more polynomials – Lieuwe Vinkhuijzen Oct 13 '16 at 21:35