Graphs — Minimum Spanning Trees (MST) VS Shortest Path Algorithms
Graphs are a type of non-linear Data Structure. I’m sure we’ve all heard of this somewhere or the other. But what differentiates them from Trees? Trees are non-linear data structures too, right? Well, in trees, each node has only one predecessor and can have more than one successor. In Graphs, each node (Vertex) can have more than one predecessor. They are connected to each other by Edges. This is what differentiates them from each other.
Graphs can be visualized as geometric shapes, forming a cycle. In the above example, we can see that there are 6 vertices (A, B, C, D, E, and F) and hence, 5 edges (N-1).
Graphs can be differentiated on the basis of many factors-
1.) On basis of geometry
· Simple Graph
· Multigraph
· Regular Graph
· Complete Graph
· Strongly Connected
· Weakly Connected
2.) On basis of Weight applied on Edges
· Non-weighted Edges
· Weighted Edges
3.) On basis of Direction of Edges
· Directional
· Non-directional
Graphs aren’t really easy to traverse through, due to the fact that they are non-linear and nodes have multiple predecessors. There are two ways to traverse through Graphs-
1.) Breadth-First Search (BFS)-
We visit the starting vertex first and then visit all the vertices adjacent to the starting vertex. Queues are an obvious choice to keep track of all nodes.
2.) Depth-First Search (DFS)-
We travel along a path in the graph and when a dead-end comes, we backtrack, sort of like trial and error. It’s like when you are in a maze & come across a dead end, you go back to where you came from and try to find a different way. Stacks are generally used for storing the nodes during traversal.
Now we have a brief idea about Graphs and how they work. Suppose you’ve been given a connected graph G with positive edge weights and you’ve been told to find a minimum weight set of edges that connects all of the vertices. This is called a Minimum Spanning Tree (MST).
It is a tree that spans all the vertices in the Graph. The total weight (cost) of the tree is also minimum.
Let’s take an example
Here, we can see all vertices are connected to each other, but the number of edges is minimized and only those edges are selected, which have the least weight/ cost.
This is the Minimum Spanning Tree of the Graph. These are also called Greedy Algorithms. Now how to find out the MST of a given Graph?
There are two main algorithms for finding the MST of a given Graph-
1.) Kruskal’s Algorithm-
· In the algorithm, we create the MST by adding the vertices and edges one at a time (Edge by Edge).
· First the edge is selected which has the least Weight/ Cost and forms the first part of the Tree.
· We keep on adding edges in ascending order of their Weights to the Tree ‘N-1’ times.
· One thing to keep in mind is that, while adding Vertices, The tree shouldn’t form a cycle.
2.) Prim’s Algorithm-
· In this Algorithm, we start with a vertex as opposed to Kruskal’s Algorithm, where we started with an Edge.
· Here too, we create the Tree one edge at a time.
· We traverse and put the vertices in the MST in such a way that we always choose the edge with the least weight.
For a graph with V vertices E edges, Kruskal’s algorithm runs in O (E log V) time and Prim’s algorithm can run in O (E + V log V) amortized time. As we can see, out of the two (Kruskal’s & Prim’s), we find that Prim’s algorithm is significantly faster in the limit when you’ve got a really dense graph with many more edges than vertices.
Whereas Kruskal’s performs better in typical situations (sparse graphs) because it uses simpler data structures.
There is one more Algorithm worth mentioning that is part of the Minimum Spanning Tree Algorithm, which is Boruvska’s Algorithm. In this, we find the closest weight edge that connects the vertices to other vertices and adds this closest edge to MST if not already added.
Looking back at what we’ve seen yet, we’ve found a tree that consists of all the Vertices of the Graph meanwhile minimizing the Cost. But what is the minimum path one can take in the Graph from one Vertex to another, which will also incorporate the least Weight. This is called the Shortest Path Problem.
In this Graph, Suppose we want to go from the Source Vertex (A) to F, the Shortest Path we can take will be (A-C-E-D-F), as the total Weight will be (2+3+4+11=20), as opposed to (A-B-D-F) where the weight will be (4+10+11=25). Naturally, one would like to take the shortest path possible (path here means anything, e.g. distance, time, or money).
There are 3 algorithms for finding the Shortest Path in any Graph.
1.) Bellman’s Ford Algorithm-
This algorithm depends on the relaxation principle where the shortest distance for all vertices is gradually replaced by more accurate values until eventually reaching the optimum solution. In the beginning, all vertices have a distance of “Infinity”, but only the distance of the source vertex = 0, then update all the connected vertices with the new distances (source vertex distance + edge weights), then apply the same concepts for the new vertices with new distances and so on.
2.) Dijkstra’s Algorithm-
This algorithm is pretty similar to Prim’s MST Algorithm & is used to find the shortest path from the Source Node to any other nodes, in a Weighted Graph.
The Algorithm-
· Set P = {Starting Vertex S} and T = {V}
· Assign the index value 0 to the starting vertex S = 0 and ∞ to all other vertices.
· Repeat.
Take the vertex v1 with a minimum index value, delete it from T, and mark it as visited.
Find the new index value of adjacent vertex v2 with respect to v1 as:
Index (v2) = Min (Index (v2), Index (v1) + w (v1, v2))
· Until T is empty.
3.) Floyd’s/ Warshall’s Algorithm-
· Time Complexity of Dijkstra’s Algorithm is O (V*V) but with the min-priority queue, it drops down to O (V+Elog(V)).
· However, if we have to find the shortest path between all pairs of vertices, both of the above methods would be expensive in terms of time.
· This is an algorithm designed for this case.
· The biggest advantage of using this algorithm is that all the shortest distances between any two vertices could be calculated in O (V*V*V), where V is the number of vertices in a graph.
So we’ve seen the various Minimum Spanning Trees Algorithms and the Shortest Path Algorithms till now. Both focus on minimizing the weights of the edges. But the outcomes are different. MSTs give Trees as Outputs whereas, in Shortest Path Algorithms, it actually gives us a path we could traverse in the Graph, with minimum Weight/ Cost.
Let’s clear it up by taking an example-
Suppose we have a Graph-
The spanning-tree looks like below. This is because if we add up the edges in this configuration, we get the least total cost possible: 2+5+14+4=25.
By just seeing the Graph, we might be thinking that this MST gives us the shortest path, but it doesn’t. If we wanted to go from 1 to 4, the cost would be 7, whereas it’s just 5, using Dijkstra’s Algorithm. This proves that MSTs are Shortest Path problems are different and should not be confused with each other.
We have seen the basics of Graphs, how they are different from Trees, Various Traversal techniques, Minimum Spanning Trees, Shortest Path Algorithms, and finally, how MSTs are different from Shortest Path Algorithms. In the end, both Algorithms have different problem statements and thus give different results. Both these algorithms have numerous applications and can be applied in our day-to-day lives.
Any system where there is a network established can implement SPTs, for eg. Telephone Wiring, Electrical Wiring, or even Internet Wiring. For efficient use of wires, taking the shortest path would be necessary, which would then subsequently reduce the cost (pun intended). Also for Drainage Systems, Water Supply, the Shortest paths are calculated. It is also used in Google Maps, where the application will calculate and show you the shortest route you can take for going from one place to another.
Hope you learned something new in this blog! Thank you for reading!