Today, graphs are used constantly in numerous programs to model and represent network-like structures. With the inherent properties of graphs as well as the numerous graph algorithms that exist, we are able to solve problems such as the shortest distance between nodes or finding the most optimal and cheapest path to traverse each node. During my time at Grace Hopper, we learned graph traversal algorithms such as DFS using recursion and BFS using queues. This piqued my interest due to its elegance, so I wanted to touch further upon graphs and delve into more technical algorithms such as Dijkstra’s and Prim’s, which I will walk through in this post.
What is it?
Dijkstra’s Algorithm is a popular algorithm for finding the shortest path between two vertices in a graph. The algorithm was created by Edsger W. Dijkstra in 1956 and has numerous real-world applications including Google Maps, network routing protocols, flighting agenda and almost all applications that require calculations of shortest distance. Understanding Dijkstra’s algorithm can also help you advance your competitive coding skills in preparation of technical interviews.
How does it work?
Consider the following weighted graph, the numbers on each edge represent the distance getting from one node to another. For example, the distance from A to B is 2, and from B to D is 7. How would you calculate the shortest path from vertex A to vertex F?
You could list out all the paths, sum up the distance for each one and find the path that yields the smallest distance, but that isn’t an efficient way especially with larger and more complicated graphs. With Dijkstra’s algorithm, we can achieve this in a few steps:
- Set all the vertices that are not directly connected to the starting vertex to infinity. If a vertex is directly connected to the starting vertex. In our case, since B and C are directly connected to A, we will keep 2 and 4 as their distances, and since D, E, F are not directly connected to A, we will assign infinity to these vertices. Therefore, our graph becomes the following:
2. Select the node (out of all the nodes we have not previously selected) with the smallest distance. In our example, we have B with distance of 2; C with distance of 4; D, E, and F with distances of infinity. Therefore, we will select B.
3. Starting from the vertex we selected from last step, find the vertices it connects to and calculate the distance it takes to arrive at that vertex. In our example, B -> D = 2+7 = 9, and B -> C = 2+1 = 3. Compare these numbers to the original numbers we wrote on the vertices and take the smaller one. For vertex D, since 9 is smaller than infinity, we would keep 9. Same thing for vertex C, we would keep 3 as the distance.
4. Repeat steps 2–3 for remaining vertices.
· Out of all the remaining vertices C, D, E, F, we select vertex C since it has the smallest distance. Then we calculate the distance from C to E (since E is the only connected vertex to C), which gives us 3+3=6. Since 6 is smaller than infinity, so we reassign vertex E with value 6.
· Next, we choose E out of the remaining vertices D, E, and F. Calculate E->D = 6+2 = 8, and replace the original 9 with 8 for D. Calculate E->F = 6+5 =11 and replace the original infinity with 11 for vertex F.
· Lastly, we choose D out of vertices D and F, then calculate the distance going from D to our target vertex F, and it gives us 8+1= 9. Since 9 is smaller than 11, 9 is the shortest distance to get to F from A, which is our final answer.
The time complexity of this algorithm is O(V²) with V being the number of vertices in the graph. However, if implanted with min-priority queue, the time complexity can come down to O (V + E logV) where V is the number of vertices and E, the number of edges.
It is also important to note that Dijkstra’s algorithm can be used on both directed and undirected graphs. However, this algorithm does not work for graphs with negative weights.
What is it?
Prim’s algorithm is a greedy algorithm used to find a minimum spanning tree in a weighted undirected graph. Minimum spanning tree (MST) is defined as the set of edges of a weighted and undirected graph that connects all vertices together without cycles and produces the smallest total edge weight. See example of minimum spanning tree below:
How does it work?
Consider the following connected, weighted and undirected graph:
Using Prim’s algorithm, we can find the minimum spanning tree of this graph with the following steps:
- Choose any vertex as the starting vertex and mark this vertex as visited. Here in this example, we choose S as our starting vertex.
2. Examine all the vertices reachable from the starting vertex, and select the edge with the least cost (weight) and mark the corresponding vertex as visited. In our example, vertices A and C are reachable from S and edge SA has a smaller weight, so we will select SA and mark A as visited.
3. We now look at all vertices reachable from S and A and elect the edge with the least cost. The edges coming from S and A are AB with a cost of 6, AC with a cost of 3, SC with a cost of 8, therefore we will select AC and mark C as visited.
4. We will repeat the above process for the newly formed tree. We will choose edge CD since it has the least cost and mark D as visited.
5. Now we can add either DB or DE to our spanning tree since they have the same costs. And for the next step when we repeat the process, we will add the other edge because 2 will still be the smallest cost. Therefore, we will end up with a minimum spanning tree and the total weight is 22.
The time complexity for this algorithm depends on the data structure it’s implanted with. If implemented with adjacency list, its runtime is O(VlogV + ElogV) with V being the number of vertices and E, the number of edges.
This is just a general rundown of both algorithms. For future posts, I will dive further into the technical aspects of the data structures (E.g. min-heap) as well as time complexity analysis that are used here. There is another algorithm, Kruskal’s, that also solves the problem of finding MSTs from a graph. This has a similar runtime but uses another data structure such as disjoint sets to greedily find the MST.