Question 2.83

53. Construct an example of a complete graph of five vertices, with distinct weights on the edges for which the nearest-neighbor algorithm starting at a particular vertex and the sorted-edges algorithm yield different solutions for the traveling salesman problem. Can you find a five-vertex complete graph with weights on the edges in which the optimal solution, the nearest- neighbor solution, and the sorted-edges algorithm solution are all different?

53.

Answers will vary.