CS502 GDB Fall 2021

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

Support your answer by writing concise and relevant comments.

#CS502 #GDB #Fall