SOLUTION: Is it C? I want to check my answers. Which of the following is one of the cheapest routes to pass through each vertex once starting and ending with Vertex "A" and using the Near

Question 1160836: Is it C? I want to check my answers.
Which of the following is one of the cheapest routes to pass through each vertex once starting and ending with Vertex "A" and using the Nearest Neighbor Algorithm.
A. ABDCA, $890
B. ACDBA, $900
C. ABCDA, $960
D. None of the Above

The graph for the question and the question itself are in the question here: i.imgur.com/xCsplh0.png
Answer by greenestamps(13200) (Show Source): You can put this solution on YOUR website!

Correct.

With the nearest neighbor algorithm, you always take the shortest/cheapest path to another vertex from the vertex you are at. With the graph shown, that is answer C.

As any good resource will tell you, the nearest neighbor algorithm will often not yield the optimal circuit, especially if it leads you to having to travel long/expensive paths near the end of the circuit.

That is exactly what happens here; the nearest neighbor algorithm has the last leg of the circuit along edge DA, which is the longest/most expensive edge in the graph.

RELATED QUESTIONS
Is it B? I want to check my answers. Which of the following best describes a... (answered by jim_thompson5910)

Is it C? I want to check my answer. Which of the following is the cheapest route to... (answered by greenestamps)

Is it A? I want to check my answer. Which of the following best describes a... (answered by jim_thompson5910)

Is it A? I want to check my answers. Which two vertices are ADJACENT to each other? (answered by greenestamps)

Is it A? I want to check my answers. Which two vertices are ADJACENT to each other? (answered by ikleyn,jim_thompson5910)

Is it B? I want to check my answers. Which Vertices have MULTIPLE EDGES? A. Vertex... (answered by MathLover1)

Is it B? I want to check my answers. Which Vertices have MULTIPLE EDGES? A. Vertex... (answered by greenestamps)

Is it B? I want to check my answers. Which Vertices have MULTIPLE EDGES? A. Vertex (answered by MathLover1)

Is it C? I want to check my answer. What is the degree of vertex A? A. 4 B. 5 (answered by MathLover1)