Prims VS Dijkstra’s : A Comparative Study

First of all as we know Prim’s is a Minimum Spanning Tree algorithm whereas Dijkstra’s algorithm deals upon finding the shortest path between nodes of a graph. So whats the problem ? Why on earth the question of comparison is coming !!!

Before addressing the question I would like give you a quick introduction on Minimum Spanning Tree & Shortest Path Algorithm.
Wikipedia goes like : A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
So, basically its a tree where there are (n-1) edges for n vertices(one edge connecting two vertices, ensuring no cycles are present) and these edges are chosen in such a way that they have the MINIMUM TOTAL COST. Yes the word “Minimum Total Cost” matters a lot !!!!

Now Lets discuss Dijkstra’s Shortest Path ALgorithm
Let’s See what wiki has to say : Dijkstra’s algorithm (or Dijkstra’s Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.The algorithm exists in many variants. Dijkstra’s original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

So to compute the minimum distance from a source to destination/destinations it forms a shortest path tree. Let’s see it with the same graph shown previously for Minimum spanning tree with A as “Source”.

WHOA!!! Both Dijkstra’s Shortest Path Tree and Minimum Spanning Tree looks the same. Let’s check what the bible of algorithm has to say on this.
Prims algorithm according to CLRS

MST-PRIM(G, w, r)
1. for each u ­∈ G.V
2.      do u.key ← ∞ 
3.         u.π   ← NIL 
4. r.key ← 0         
5. Q ← G.V   
6. while Q ≠ Ø
7.    do u ← EXTRACT-MIN(Q)
8.       for each v ∈ G.Adj[u]
9.           do if v ∈ Q and w(u, v) < v.key then 
10.             v.π ← u
11.             v.key ← w(u, v)

Working of Prims Algorithm
Names that are used in the pseudo-code
G-> Graph function.
w-> Weight Matrix of the Graph denoting distance b/w any two vertices.
r -> The starting vertex or root of the spanning tree.
v.key->Minimum weight connecting vertex ‘v’ to another one already added in a tree.
π -> Parent function of each vertex so as to trace the tree at last.
Q->A min-heap or a PriorityQueue based on the key attribute of each vertex.
Adj->Adjacency matrix of G.

In line 1 a for loop starts which initializes every vertices with key of infinity and parent as null, because none of the vertices are included in a tree.

In Line 4 the minimum weight of the root is changed to ‘0’ ensuring that it should be picked up first by the Min PriorityQueue.

In Line 5 the Queue is fed with all the nodes/vertices in the graph and it will take decision with respect to the ‘key’ attribute. Once a vertex gets ejected from the queue it will get its place in the Minimum Spanning Tree.

In Line 6 The process starts and continues until the queue is empty which means this loop will execute n times for ‘n’ number of vertices.
Each time a vertex is extracted by the EXTRACT_MIN operation of a MIN_HEAP and the one with the lowest key is added to the tree.

In Line 8 we can see once a vertex is obtained from the Queue , it’s neighboring vertexes are iterated.

In Line 9 two conditions are checked over those neighboring vertexes
➡️ Firstly, if the vertex is already present in the Queue, with this test it can be ensured that if the vertex is still present in the Queue then it is not present in the tree.
➡️ Secondly, if the distance between the neighboring vertex and the extracted vertex(the newly added vertex) is less than the present distance of the neighboring vertex.

If both conditions are satisfied then the parent and the key of this neighboring vertex is updated in the subsequent lines.

So this is how the Prim’s algorithm works , each time a connected edge with lowest weight is chosen and this is how it makes the entire spanning tree to be of Minimum Total Cost.

Working of Dijkstra’s Algorithm

1. for each u ­∈ G.V
2.     do u.key ← ∞ 
3.        u.π ← NIL 
4. r.key ← 0 
5. Q ← G.V 
6. while Q ≠ Ø
7.    do u ← EXTRACT-MIN(Q)
8.       for each v ∈ G.Adj[u]
9.           do if v ∈ Q and w(u, v)+ u.key < v.key then 
10.             v.π ← u
11.             v.key ← w(u, v) + u.key

Now as we can see the entire pseudo-code is same as the Prim’s algorithm except line 9 & 11(bolded text).
Line 9 to 11 is known as the Relaxation Step of Dijkstra’s Algorithm. Here the cumulative summation of the extracted vertex key(u.key) value along with distance between the extracted vertex and the neighboring vertex(w(u, v)) are checked and if it is less than the present distance of the neighboring vertex(v.key) then v.key is assigned to that new summation.

Why by simply adding “u.key” the entire algorithm is getting changed ?
The summation shows that the Dijkstra’s algorithm is not only considering the edge of a new vertex(as in prims where a new vertex having the lowest edge is selected), it is considering the entire distance from source to that vertex.
With the help of “key” it keeps track of the present minimum distance from the source to that vertex(later this distance can be changed). So instead of minimizing the total length of the network it is trying to minimize the length of the distance between a specific source and vertex. It will keep the edges in the shortest path tree in such a way so that if we go to any vertices from the mentioned source we will get minimum length but it does not guarantee minimum length of the total network of the shortest path tree. So this algorithm is also known as “Single Source Multiple Destination Shortest Path”.

Let’s See an example to clearly understand the difference.

Dijkstra’s Algorithm where Bold Lines are added in the Shortest Path Tree and Dotted Lines are presently in the MIN-Heap.

Prim’s Algorithm for the same graph but with different result.

So as we can see from the above example Node “AD” is making the difference In Shortest Path Tree node “AD” is selected but in Minimum Spanning Tree it is not.
Total Length of Shortest Path Tree is : 4+4+5 = 13
Total Length of Minimum Spanning Tree is : 4+4+4 = 12
Hence, the minimum spanning tree is giving minimum value for the total length of the network.

Now for Minimum Spanning Tree,
Length of AD = AC+CD = 4+4 =8
For Shortest Path Tree
Length of AD= 5
Hence, the Shortest Path Tree is giving minimum distance between node A & D, whereas spanning tree is failing to give the minimum length between two vertices.

This is the main difference between Dijkstra’s Algorithm and Prims Algorithm.
In Dijkstra’s Algorithm edge “AD” is getting selected because the source “A” is connecting “D” with a length of 5 which is lowest with respect to “AC” + “CD” is 8.
In prim’s as total distance summation are not taken 5 is compared with 4(not with 8) and hence edge “CD” is selected over “AD”.

Time Complexity of both the algorithm is O(|V|+|E|)log |V| where V & E are number of vertices & number of edges respectively. The logarithmic factor is coming because of the Extract MIN function of a MIN Heap.

Finally to conclude, in layman’s language If you are asked to calculate minimum cost of building roads in a graph network then go for Minimum Spanning Tree whereas If you are asked to build roads from a particular city so as to minimize distances to other cities then go for Dijkstra’s.