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.

Data Scientist and Writer, passionate about language

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store