Question

use the complete weighted graph shown to answer the question.

using the nearest neighbor method starting with vertex a, which of the following is an approximate optimal solution?
i. a, b, c, d, a
ii. a, c, b, d, a
iii. a, d, b, c, a
iv. a, d, c, b, a

Explanation:

Identify edge weights from starting vertex A

$$
LATEXBLOCK0
$$

Select nearest unvisited neighbors sequentially

$$
LATEXBLOCK1
$$

Complete the circuit back to starting vertex A

$$
LATEXBLOCK2
$$

Answer:

• I. A, B, C, D, A
• II. A, C, B, D, A
• III. A, D, B, C, A
• IV. A, D, C, B, A (Correct answer)