Question

6. Solve the Traveling Salesperson Problem using the Cheapest Link Algorithm: A 24 B

Answer 1

The cheapest Algorithm says, it should not form a circuit until and unless it connect with all the given vertices.

Fig :2 in the given image is showing the resultant circuit. and the path is,

A-B-C-D-E-A

or B-C-D-E-A-B

or C-D-E-A-B-C

or D-E-A-B-C-D

or E-A-B-C-D-E

Note: We can start from any vertex of Fig 2 (given in the screenshot)

3 Solution : A 249 25 28 Listing all weight frown low to high cheapest Algorithm 8. D-cu o 9 , B-cu . A. 24 & Eigis? 10. A- & v . i forming thcuit, w-Cannot 9A-B . Consider i HX 25, (Same reason 28, T 287 30 X (we don't care are before that only we Aedd Constraints = found a tercait connecting we have to chouse All circuit inualving all 5 vertices. A-B-C-D-E-A - Note: We can start and and from any een the vertices of figl given ahonda CScanned with CamScanner