Prim , Kruskal or Dijkstra

Question

I've a lot of doubts on these three algorithm , I can't understand when I've to use one or the other in the exercise , because the problem of minimum spanning tree and shortest path are very similar . Someone can explain me the difference and give me some advice on how I can solve the exercise? Thank you so much.

Answer 1

I start in Washington DC and I want to travel to Roanoke. What is the shortest way to get there? This is a case where you would want to use Dijkstra's Algorithm.

I live in Roanoke. We got a large snowstorm and have to plow the roads. What roads do we plow to enable everyone to travel to any location in the city? Here, we aren't concerned with a single shortest path, but the overall minimum cost in plowing roads to enable a path from every two points in the city. This is the minimum spanning tree problem. Notice that a tree is a minimally connected graph (in terms of the number of edges). The MST minimizes the cost of the tree, based on the edge weights.

Answer 2

Prim and Kruskal are for spanning trees, and they are most commonly used when the problem is to connect all vertices, in the cheapest way possible.

For Example, designing routes between cities.

Dijkstra, is for finding the cheapest route between two vertices.

For Example, GPS navigation.