Dijkstra’s Algorithm in Python: digital mapping at a drag convention
Let’s start with the pronunciation…
Dijkstra’s Algorithm is pronounced “dike-struh’s” algorithm and is named after the computer scientist, Edward Dijkstra. It is a weighted graph search algorithm that finds the shortest path from the source vertex to all other vertices in the graph. This algorithm has some interesting real-world applications. The first application it is usually associated with is digital mapping. Services like Google Maps rely on finding the shortest path between two points, so its users are able to get where they need to go in a timely fashion. It’s costly to waste time on the longest route anywhere. Dijkstra’s Algorithm speaks to that. It takes into consideration the cost of the path to the goal. That’s why this algorithm is also referred to as a “greedy algorithm”. Greedy algorithms make the optimal choice at that given moment and do so without knowing any future outcomes. The algo is only concerned with the current optimal solution.
A real-world example:
The world of geolocation and digital mapping implements this algorithm consistently. From GPS to automated delivery drone paths to planning flight paths for airline companies. I personally find it quite interesting. As a simple implementation, I will create an example surrounding drag queen booths at my favorite drag show convention. Now like any good convention, there are a lot of booths I’m going to want to visit in a timely fashion. I want to find the shortest route between Tayce’s booth and Katya’s booth. For the sake of simplicity, Let’s imagine these booths are all connected by pathways and there aren’t any other super fans in my way. Clear walkways for days.
For clarification, each convention booth is a vertex or node on the graph. Each pathway is an edge in the graph and each pathway has a value. Dijkstra’s algo will choose the lower of the values when given a choice between paths/edges. Oh and obviously I can’t walk in a straight line from Tayce’s convention booth to Katya’s convention booth because then I wouldn’t need the algorithm and I would also miss the other booths I wanna quickly grab merch from. I’ve mapped out 3 possible paths. They are as follows.
- Tayce > Pearl > Mo Heart > Katya
- Tayce > Raja > JuJubee > Trinity K. Bonet > Katya
- Tayce > Raja > JuJubee > Trinity K. Bonet > Spanky Jackson -> Katya
All paths lead to Katya Zamolodchikova. They each, however, have different values. Dijkstra’s Algorithm will help me find the lowest value and thus the quickest route to see one of my favorite drag queens of all time.
Applying Dijkstra’s Algorithm:
The starting point (node) in my graph is Tayce’s booth. The distance between Tayce’s booth and itself is 0. The distance between Tayce’s booth and all other booths will be set to infinity. After this initialization of the algorithm, we can iterate through the next steps until all booths (nodes) are visited and weights (values) set for each edge (path). Starting out, we choose the booth with the smallest value as the “current node”. Then as the other nodes are visited, the distance between is updated. Once all nodes are visited and once all distances are recorded, the start node has its final cost for the algorithm.
Sticking with my example, Tayce’s booth has a distance value of 0. The booths that are closest (the neighbors) are Pearl’s booth and Raja’s booth. I started with a value of infinity (an unknown) for the distance between Tayce and the other booths. Now that paths have been set and are being explored, the values will change. The value for Pearl’s booth will be updated to 4. The value for Raja’s booth will be updated to 5.
Get Skull and Zen™️’s stories in your inbox
Join Medium for free to get updates from this writer.
Before continuing, Tayce’s booth will be marked as “visited”. The final cost is 0. The closest neighbor to Tayce is Pearl’s booth. The algorithm repeats and now Pearl’s neighbors are marked as “visited”. Pearl’s neighbors are Tayce and Mo Heart’s booth. Tayce’s booth has already been “visited” so Mo Heart’s booth is the one explored. Mo Heart’s value will be updated by adding the value of the edge (path) connecting Pearl to Mo Heart (3) and Mo Heart’s booth (4), which results in a value of 7.
Now Mo Heart’s booth is marked as “visited” and the algo chooses the next node, Raja’s booth. The neighbors of Raja’s booth are visited, and values updated. Some previous values are updated when better routes are revealed. After more iterations and calculations, the model will return the best route for me which is Tayce -> Pearl -> Mo Heart -> JuJubee -> Trinity K. Bonet -> Katya. This path ultimately has a value of 11. I’m just excited to see Katya! Lol
Let’s talk Python code
The first part of the code is an implementation of the graph we need to start our measurements. This Graph class is administered as a dictionary. The keys of the dictionary are the convention booths and the key’s values are the recorded distances to other booths (nodes) on the graph.
Next, Dijkstra’s Algorithm is defined. A function is implemented to initialize the equation. The function will take in two arguments: graph and start_node. The graph argument calls to the instance of the Graph class created above. The start_node argument is the booth (node) at the starting point of the algorithm. Then the get_nodes() method initializes a list of all unvisited nodes. We need to use a while-loop because Dijkstra’s Algorithm must execute on all possible paths to visit all the nodes on the graphs.
To print out the results, we create a function that takes the two dictionaries returned by the Dijkstra’s function written above and uses them to find the best possible path and its score.
Finally, we can initialize the booths (nodes) and their paths (edges), using the values in creation of a Graph class. Then we pass it the Dijkstra’s function we created and print some sweet results!
Wonderful! This is such a great route to take to see my favorite Queens. Thanks to Dikstra’s Algorithm and Python. So cool.
Interested in more info?
If you enjoyed this brief tutorial, please follow me, Z. Myricks, for more guides in all things Python. Make sure to follow Plain Simple Software for more software articles!
