Question

Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex C. 

a. List the vertices in the Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends. 

b. What is the total weight along the Hamiltonian circuit?

Answer 1

a. C D B E C

b. 34

Explaination :

Hamiltonian circuit states that every vertex is visited exactly once except the starting vertex as it'll be the end vertex as well. Each vertex can't be visited more than once.

Nearest neighbor algorithm suggests that we consider a vertex and see the costs to it's neighbors(edges). We pick the edge with lowest cost which means it's the nearest.

By using this algorithm the above problem is solved as follows :

Vertex C is the starting point

Now looking at it's neighbors, D is the shortest to go to hence C-D = 9

Looking at D's neighbors, B is the shortest to go to hence D-B = 6

Looking at B's neighbors, E is the shortest to go to hence B-E = 8

Now all vertices are visited once, time to go back to the starting hence E-C = 11

The path is CDBEC

Adding up all the costs of edges we get 9+6+8+11 = 34 is the length of the Hamiltonian circuit.

comment for any clarifications!