That's the Travelling Salesman problem, which is NP-Complete. You won't find a non-probabilistic algorithm that's better than O(k^N) because none has been found.