CODEWITHSUNDEEP
algorithmgraphlanguage-agnostictraveling-salesman
ayushgp
ayushgp

Reputation: 5101

Finding Hamiltonian path vs Hamiltonian circuit in a complete undirected weighted graph

I have a complete graph(Adj. matrix) with weights. I have built a solution for finding the minimum hamiltonian circuit in this graph(Travelling salesman problem) using branch and bound. I'm now stuck at finding the best hamiltonian path with given start and end nodes. Without given start and end nodes, the best solution would be the hamiltonian circuit - longest edge in the circuit.

I could not think of a solution other than simply brute forcing to find best hamiltonian path with given start and end nodes. Please provide some pointers to how to proceed with this problem.

Upvotes: 1

Views: 765

Answers (2)

BKE
BKE

Reputation: 573

A given start node and end node is equivalent to the constraint that the directed edge between the end node and the start node must be part of the TSP tour.

So you can simply change your adjacency matrix:

  • set all outgoing edges from the desired end node to infinite weight, except the edge to the start node
  • set all incoming edges to the desired start node to infinite weight, except the edge from the end node
  • set the edge from the start node to the end node to infinite weight as well (to make sure you do not get the reverse solution, which might be different if your adjacency matrix is not symmetric)

This is very similar to the branching method your implementation uses.

Upvotes: 1

n. m. could be an AI
n. m. could be an AI

Reputation: 120239

Add a large constant to the weight of every edge except the one between the given start and end node, which should be set to zero. The constant can be chosen as N*maxweight where N is the number of vertices and maxweight is the maximal edge weight. This guarantees that the given edge will be included in the circuit.

Upvotes: 0

Related Questions