Difference in the application of Dijkstra and Prim algorithms
What is the basic difference in the field of application of dijsktra and Prim algorithms? What problems does one of them solve that the other cannot solve? Having, for example, the following situation: it is necessary to find the smallest possible traffic path that passes through all the sights of a city, and the distance between these sights is known. What would be the best algorithm to solve this type of problem?
1 answers
The original algorithm proposed by Dijkstra serves to find the smallest path from an initial node to an end node. However, the most commonly used Dijkstra algorithm is a variant that finds the smallest path from one 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:
Or prim algorithm it serves to find the minimum generating Tree of a graph. The minimum generating tree is the related Subgraph with the smallest sum of the weight of the edges and containing all the nodes of the original graph. So if the graph has redundant edges, they are taken so as to obtain the minimum sum of the weights.
If an electricity distributor wants to connect all the houses in a region so that the wires travel the shortest possible distance the ideal connections can be determined with a prim algorithm. The same can be true for planning the location of optical fibers in an internet network or for connecting several cities with a minimum of roads.
The following figure shows a complete graph and its minimum generating tree:
So the two algorithms are for distinct 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 clerk problem traveling salesman problem with repetition. This is an NP-difficult problem and putting his solution here would make the answer too big. In case you want the solution of this problem I suggest you open another question that I will be happy to answer.
Prim's algorithm doesn't help much in this problem, at least I've never seen a TSP solution using it. Already Dijkstra's algorithm can be used to determine the minimum cost of all paths two to two, which is a part of solving the problem, but is usually not used to solve the TSP without repetition.