Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
