Difference in the application of Dijkstra and Prim algorithms

Question

What is the basic difference in the field of application of Dijsktra and Prim algorithms? What problems does one solve that the other cannot solve? Having, for example, the following situation: it is necessary to find the shortest possible transit path that goes through all the sights of a city, and it is known the distance between these sights. What would be the best algorithm to solve this type of problem?

Answer 1

The original algorithm proposed by Dijkstra serves to find the shortest path from an initial node to a final node. But the most widely used Dijkstra algorithm is a variant that finds the shortest path from an initial node to all other nodes in the graph. In general this algorithm will be used in shortest path problems (Shortest Path).

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

Prim’s algorithm serves to find the minimum generating tree of a graph. The minimum generating tree is the connected subgraph with the smallest sum of the edge weight and containing all nodes of the original graph. So if the graph has redundant edges, they will be drawn so as to obtain the minimum sum of weights.

If an electric power distributor wants to connect all the houses in a region so that the wires run as close as possible the optimal connections can be determined with a Prim algorithm. The same may be true for planning the location of optical fibers on an internet network or for connecting several cities with minimal roads.

The following figure shows a complete graph and its minimum generating tree:

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 traveling salesman problem with vertex repetition (Travelling salesman problem with Repetition). This is an NP-hard problem and putting his solution here would make the answer too big. If 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. Dijkstra’s algorithm can be used to determine the minimum cost of all two-way paths, which is a part of solving the problem, but is generally not used to solve TSP without repetition.