Difference between Prim's and Dijkstra's algorithms?

Question

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Solution 1

Prim's algorithm constructs a minimum spanning tree for the graph, which is a tree that connects all nodes in the graph and has the least total cost among all trees that connect all the nodes. However, the length of a path between any two nodes in the MST might not be the shortest path between those two nodes in the original graph. MSTs are useful, for example, if you wanted to physically wire up the nodes in the graph to provide electricity to them at the least total cost. It doesn't matter that the path length between two nodes might not be optimal, since all you care about is the fact that they're connected.

Dijkstra's algorithm constructs a shortest path tree starting from some source node. A shortest path tree is a tree that connects all nodes in the graph back to the source node and has the property that the length of any path from the source node to any other node in the graph is minimized. This is useful, for example, if you wanted to build a road network that made it as efficient as possible for everyone to get to some major important landmark. However, the shortest path tree is not guaranteed to be a minimum spanning tree, and the sum of the costs on the edges of a shortest-path tree can be much larger than the cost of an MST.

Another important difference concerns what types of graphs the algorithms work on. Prim's algorithm works on undirected graphs only, since the concept of an MST assumes that graphs are inherently undirected. (There is something called a "minimum spanning arborescence" for directed graphs, but algorithms to find them are much more complicated). Dijkstra's algorithm will work fine on directed graphs, since shortest path trees can indeed be directed. Additionally, Dijkstra's algorithm does not necessarily yield the correct solution in graphs containing negative edge weights, while Prim's algorithm can handle this.

Hope this helps!

Solution 2

Dijkstra's algorithm doesn't create a MST, it finds the shortest path.

Consider this graph

       5     5
  s *-----*-----* t
     \         /
       -------
         9

The shortest path is 9, while the MST is a different 'path' at 10.

Solution 3

Prim and Dijkstra algorithms are almost the same, except for the "relax function".

Prim:

MST-PRIM (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Dijkstra:

Dijkstra (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

The only difference is pointed out by the arrow, which is the relax function.

• The Prim, which searches for the minimum spanning tree, only cares about the minimum of the total edges cover all the vertices. The relax function is alt = w(u,v)
• The Dijkstra, which searches for the minimum path length, so it cares about the edge accumulation. The relax function is alt = w(u,v) + u.key

Solution 4

Dijsktra's algorithm finds the minimum distance from node i to all nodes (you specify i). So in return you get the minimum distance tree from node i.

Prims algorithm gets you the minimum spaning tree for a given graph. A tree that connects all nodes while the sum of all costs is the minimum possible.

So with Dijkstra you can go from the selected node to any other with the minimum cost, you don't get this with Prim's

Solution 5

The only difference I see is that Prim's algorithm stores a minimum cost edge whereas Dijkstra's algorithm stores the total cost from a source vertex to the current vertex.

Dijkstra gives you a way from the source node to the destination node such that the cost is minimum. However Prim's algorithm gives you a minimum spanning tree such that all nodes are connected and the total cost is minimum.

In simple words:

So, if you want to deploy a train to connecte several cities, you would use Prim's algo. But if you want to go from one city to other saving as much time as possible, you'd use Dijkstra's algo.

View more solutions

Comments

[JW.ZG]

The best way to distinguish their difference is read some source code, Dijkstra and Prim. The main difference is here: for Prim graph[u][v] < key[v], and for Dijkstra dist[u]+graph[u][v] < dist[v]. So as you can see from the graphs in those two pages, they are different mainly because of these two lines of code.

[e4c5]

Possible duplicate of What is the difference between Dijkstra and Prim's algorithm?

[greybeard]

Meta difference: I think there's just one algorithm designated Prim's, but multiple Dijkstra's, one being notorious for variations.

[anuj pradhan]

Ok thanks ...you cleared a good point to notice. Till now i was considering that the output generated by dijkstra will be a MST but you cleared the doubt with a good example .I can see clearly if i will find a MST using say 'kruskal' then i will get the same path as you mentioned. Thanks a lot

[Bernhard Barker]

More correctly - The shortest path is 9 ... from s to t. The weight of the graph generated by Dijkstra's algorithm, starting at s, is 14 (5+9).

[dfb]

@Dukeling - Huh? the weight of the tree/graph in Dijkstra's is meaningless, that's sort of the point....

[Bernhard Barker]

@dfb You were proving it's not an MST, so the weight is important for that. As in 14 > 10, so it's not an MST.

[Ram Narasimhan]

Very succinctly illustrated!

[tmyklebu]

"Dijkstra is concerned with only two nodes" is bunk.

[Ankit Roy]

@dfb: Normally we only run Dijkstra's algorithm to get the shortest path between a specific pair of vertices, but in fact you can keep going until all vertices have been visited, and this will give you a "shortest path tree", as templatetypedef's answer explains.

[amirouche]

Thanks! The exit is nebulous, why does it exit the loop even if nothing happens?

[nethsix]

At the code level, the other difference is the API. Prim has method edges() to return MST edges, while Dijkstra has distanceTo(v), pathTo(v), which respectively returns distance from source to vertex v, and path from source to vertex v, where s is the vertex your initialize Dijkstra with.

[nethsix]

Corollary, initializing Prim with any any source vertex, s returns the same output for edges(), but initialization Dijkstra with different s will return different output for distanceTo(v), pathTo(v).

[Akhil Dad]

Does prims allow negative weight? if yes than this is another difference. I read that you can allow negative weights on prim's by adding large positive no. to each value, making it all positive.

[JW.ZG]

The first paragraph makes no sense, man. The question is what's the difference between Dijkstra and Prim, where Dijkstra is not about what you said the length of a path between **any** two nodes, you should just focus why the distance between src node and any other nodes in Prim is not shortest if it is not shortest. I think he must be asking the src node in Prim to any other node. Why did you talk about any two nodes in Prim? That's of course not the shortest.

[templatetypedef]

I've cleaned up the wording in the paragraph about Dijkstra's algorithm to clarify that the shortest path tree is only a minimizer for shortest paths originating at the source node. The reason I've structured my answer this was way to illustrate what the algorithms find rather than how they work to show at a higher level why they produce different outcomes and why you wouldn't expect them to be the same.

[information_interchange]

To see why Dijkstra's and Prim's might not return the same thing, consider a radial graph with a center node connected to say 4 other nodes, each with weight 3. Then, imagine that between two of those non-central nodes, there is an edge with weight 4. The shortest path between those two nodes is via the direct connection, but this edge will not be included in the MST.

[Dhananjay Sarsonia]

Solved my confusion! Perfect Answer!!

[Deepak Yadav]

The simplest explanation is in Prims you don't specify the Starting Node, but in dijsktra you (Need to have a starting node) have to find shortest path from the given node to all other nodes. See stackoverflow.com/a/51605961/6668734

[Mr X]

here the processed vertex has to ignored for undirected graph

[Peter]

I don't understand this graph thou, can someone tell me what is this ?

[Amelio Vazquez-Reina]

@DeepakYadav Some definitions of Prim's (e.g. CLRS') assume that you actually provide a starting vertex. You may instead say that Prim's returns an MST (and thus solves the stated problem) regardless of what vertex you start with, whereas in Dijkstra's, providing different vertices solves different (single-source) shortest path problems.

[Amelio Vazquez-Reina]

@templatetypedef - When you say: "and the cost of building such a tree [with Dijkstra] could be much larger than the cost of an MST." can you please elaborate?

[templatetypedef]

@AmelioVazquez-Reina Sorry, that bit is ambiguous. What I meant is that the sum of the weights on the edges of a shortest-paths tree can be much larger than the sum of the weights on the edges in an MST.

[Amelio Vazquez-Reina]

+1 Thanks. That's actually what I assumed you meant :). I think if you replace that sentence with exactly what you wrote, this answer will be even clearer/better.

[templatetypedef]

Yep, just did that.

[fkotsian]

Incredible answer! Had an intuition that the two algos were extremely similar but couldn't put my finger on exactly how - thanks for this beautiful answer!

[LomoY]

@templatetypedef Thanks for the explanation, one more thing I want to add to this answer. Prim could handle negative edges, while Dijkstra can only work on graphs with positive edges.

[Zack Light]

I think @AkhilDad is right about the second difference. Also, I think the pseudocode needs a bit of logic to check if a node has been visited before or not