2
$\begingroup$

I have implemented a branch and bound algoritm for finding a Hamiltonian cycle in my software, but I actually need to find a shortest route from fixed vertex through all verticies ending at any of them.

As far as I understood, I can reduce closed-cycle TSP to open-cycle with fixed starting point by adding dummy vertex. But I can't find or figure out the weights of the edges of this vertex.

How can I do this?

$\endgroup$
2
$\begingroup$

Add two dummy vertices, $d_1,d_2$. Add edges of weight 0 from all other vertices to $d_1$. Add an edge of weight 0 from $d_1$ to $d_2$. Add an edge of weight 0 from $d_2$ to your fixed starting vertex. (If you need a complete graph, each missing edge can be replaced by an edge with weight $+\infty$ or some very large positive weight.) Then any Hamiltonian cycle in the resulting graph will correspond to a Hamiltonian path in the graph that starts at your fixed vertex.

$\endgroup$

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.