# How to get initial flow for TSP with missing edges

I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing.

How do I generate a valid initial path effectively?

I would use a greedy algorithm, but I can't be sure it will result in a valid path. I could still use it and hope that simulated annealing will find a valid path, but I can't guarantee that it will.

Set the cost on the missing edges to $+\infty$, or some suitably large constant. Then all paths are valid, and you can apply simulated annealing. Simulated annealing will have a very strong incentive to avoid those edges.

In general, you cannot expect any algorithm to both (a) be guaranteed to find a valid path, and (b) be guaranteed to terminate in a reasonable amount of time. That's because finding a valid path is the Hamiltonian path problem, which is NP-hard -- so even finding a single path could be extremely hard, depending on the input graph. Since you presumably want an algorithm that terminates in a reasonable amount of time, that means you'll have to accept the possibility that the algorithm fails to output a valid path. (If not, then you'll have to accept the possibility that the algorithms fails to terminate in your lifetime, which seems just as bad.)