# Difference in the application of Dijkstra and Prim algorithms

6

What is the basic difference in the field of application of the Dijsktra and Prim algorithms? What problems does one of them solve that the others can not solve? Having, for example, the following situation: it is necessary to find the smallest possible transit route that passes through all the tourist points of a city, being that the distance between these tourist points is known. What would be the best algorithm to solve this kind of problem?

asked by anonymous 15.04.2016 / 04:37

8

The original algorithm proposed by Dijkstra is to find the smallest path from an initial node to an end node. However, the most used Dijkstra algorithm is a variant that finds the smallest path from an initial node to all other nodes in the graph. In general this algorithm will be used in shortest path problems.

The following figure shows the result of the algorithm with the shortest distance from the root to each node:

ThePrimalgorithmisusedtofindtheminimumgeneratingtreeofagraph.Theminimumgeneratingtreeistheconnectedsubgraphwiththesmallestsumoftheweightoftheedgesandwhichcontainsallthenodesoftheoriginalgraph.Thereforeifthegraphhasredundantedges,theywillbedrawninordertoobtaintheminimumsumoftheweights. 