Question

Suppose he starts travel from source city ‘A’, visit different cities in the following ways:

• A à C à B à D
• A à D à C à B
• A à B à D à C

Considering the above scenario, you have to choose a suitable algorithm from the following list of algorithms which you think is the best algorithm for the salesman to cover maximum cities by traveling minimum distance.

• Prim''s Algorithm
• Dijkstra''s Algorithm
• Bellman-Ford Algorithm
• Floyed-Warshall Algorithm
• Johnson''s Algorithm

Answer 1

The most optimal path to reach from one node to another is the direct path, rather than the connecting path.It is always less than or equal path $d(i,k)$ + $d(k, j)$

The most feasible algorithm for the traveling salesman problem is Prim's algorithm.

Algorithm to use the minimum spanning tree

1. Let the starting and the ending point of the be 1
2. We need to construct a MST as a root with 1 by using the prim's algorithm.
3. Make a list of the already visited node and construct MST and add 1 at the end.