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?
Difference in the application of Dijkstra and Prim algorithms
6
asked by anonymous 15.04.2016 / 04:37
1 answer
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.
IfanelectricaldistributorwantstoconnectallthehousesinaregionsothatthewiresruntheshortestpossibledistancetheidealconnectionscanbedeterminedwithaPrimalgorithm.Thesamecanbedonetoplanthelocationoffiberopticsinaninternetnetworkortoconnectseveralcitieswiththeminimumofroads.
Thefollowingfigureshowsacompletegraphanditsminimumgeneratingtree:
So the two algorithms are for different purposes and you will hardly have a problem where you will have to choose to use one or the other.
The problem you described is the problem of the traveling salesman problem with repetition. This is an NP-hard problem and putting his solution here would make the answer very big. If you want to solve this problem I suggest you open another question that I will be happy to answer.
The Prim algorithm does not help much in this problem, at least I've never seen a TSP solution using it. The Dijkstra algorithm can be used to determine the minimum cost of all paths two to two, which is a part of the solution to the problem, but is not usually used to solve the TSP without repetition.
11.08.2016 / 02:04