Answer to Question #162208 in Algorithms for ifra

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

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.