For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A?
A) 215
B) 220
C) 235
D) 295

Question

For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A? 
A) 215 
B) 220 
C) 235 
D) 295

Quizplus · Accepted Answer

Starting at vertex A, the nearest-neighbor algorithm chooses the edge with the smallest weight each time. 
A-B: weight 50 
B-D: weight 65 
D-C: weight 60 
C-G: weight 25 
G-F: weight 20 
F-H: weight 25 
H-E: weight 20 
E-A: weight 45 
Total cost = 50+65+60+25+20+25+20+45 = 220. Therefore, the answer is choice B.

For the Graph Below, What Is the Cost of the Hamiltonian