Question

Please help! Correct answer only, please! 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

Answer 1

Answer: c) ABCDA, $960

Explanation:

The nearest Neighbor Algorithm states to choose the next vertex based only on the weights of the neighbor of that vertex.

Starting at A: Options are B = 220, C = 240, D = 310

Choose B because it has the smallest value.

From B: Options are C = 200, D = 210

Choose C because it has the smallest value.

From C: There is only one option --> D = 230 (we cannot choose A because it was our starting point and we haven't touched every vertex, yet).

From D: We touched all of the vertices so return to the starting point, A = 310

A → B → C → D → A --> 220 + 200 + 230 + 310 = 960

Notice that if we looked at the entire circuit first, this is NOT the optimum path. But this is the result using the Nearest Neighbor Algorithm.