Answer to Question #162657 in Algorithms for wardah

Question

A salesman wants to travel among 4 or n cities. He wishes to visit maximum or all cities in one day. The order of visiting different cities is not important, but his point of consideration is to minimize distance travelled. In a map this scenario can be described in this way; Cities are represented by nodes, and distance is represented as edges.

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

I think, the best algorithm for the salesman is Prim''s Algorithm.

Algorithm finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.