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