Dijkstra’s Shortest Path Algorithm
If you’ve been following my blogs, you’ll know that I’ve been trying to level up my programming skill set. During an interview, I was recently asked a question about adjacency networks for a node map. Some of you will know what this question pertains to — Dijkstra’s Algorithm.
This is a question that may come up if you work in data engineering, as this is closer to the engineering side rather than to the analysis side. I had some difficulty explaining my solution to the interviewer, without any kind of notion of input, so I wanted to try to give it a try in this blog post.
The YouTuber Computer Science had a great explanation here. I’m going to put his verbal explaination into my own words below.
You start with an origin, and a list of the other nodes, perhaps in a tuple with what their distance is from the origin. Because you want to find the shortest path, you will be using a check to find whether a new distance is shorter. Therefore, you will want to set the distances to a high number or infinity. You also want to have an empty list for your visited nodes and a list of all unvisited nodes.
The primary loop of the algorithm runs as follows:
1. Visit each node with the smallest known distance from the start vertex. In this case, on the first loop it will be the origin
2. For the current vertex (the one you’re visiting), examine its unvisited neighbors.
3. Calculate the distance from each unvisited node to the start node. On our first stop, the origin 1, we would calculate the distance from 1 to 2 as 2, 1 to 3 as 5 and from 1 to 4 as 2.
4. If the calculated distance is less than the known distance, update the shortest distance
5. Update the previous vertex for each of the updated distances
6. Add the current vertex to the list of visited vertices
The loop will stop when all of the vertices are visited.
Watching this video definitely helped me verbalize what I had tried to during my interview. It was an important lesson to remember; your ability to communicate a solution and its pros and cons is almost as important as your ability to solve a problem.
Thanks so much for reading! I’ll see you next week.
