Implementing Dijkstra’s Algorithm in Python
What do GPS navigation devices and websites for booking flights have in common? As it turns out, a lot! For one, both technologies employ Dijkstra’s shortest path algorithm.
In this article, we’ll give an overview of Dijkstra’s algorithm and provide an easy-to-follow implementation in Python. After we lay out the explanation in plain English, you’ll see that the Python implementation is not that much different.
What Is Dijkstra’s Algorithm?
In 1956, Dutch programmer Edsger W. Dijkstra had a practical question. He wanted to figure out the shortest way to travel from Rotterdam to Groningen. But he did not simply consult a map to calculate the distances of the roads he would need to take. Instead, Dijkstra took a computer scientist’s approach: he abstracted from the problem by filtering out the specifics such as traveling from city A to city B. This allowed him to discover the more general problem of graph search. Thus, Dijkstra’s algorithm was born.
Dijkstra’s algorithm is a popular search algorithm used to determine the shortest path between two nodes in a graph. In the original scenario, the graph represented the Netherlands, the graph’s nodes represented different Dutch cities, and the edges represented the roads between the cities.
You can apply Dijkstra’s algorithm to any problem that can be represented as a graph. Friend suggestions on social media, routing packets over the internet, or finding a way through a maze—the algorithm can do it all. But how does it actually work?
Dijkstra’s Algorithm: Problem Setting
Recall that Dijkstra’s algorithm operates on graphs, meaning that it can address a problem only if it can be represented in a graph-like structure. The example we’ll use throughout this tutorial is perhaps the most intuitive: the shortest path between two cities.
We’ll be working with the map below to figure out the best route between the two European cities of Reykjavik and Belgrade. For the sake of simplicity, let’s imagine that all cities are connected by roads (a real-life route would involve at least one ferry).
Note the following:
- Each city is represented as a node.
- Each road is represented as an edge.
- Each road has an associated value. A value could be the distance between cities, a highway toll, or the amount of traffic. Generally, we’ll favor edges with lower values. In our specific case, the associated value is defined by the distance between two cities.
You also may have noticed that we cannot reach Belgrade from Reykjavik directly; that would render our exercise pointless. But there are several paths from Reykjavik to Belgrade that go through other cities:
- Reykjavik –> Oslo –> Berlin –> Belgrade
- Reykjavik –> London –> Berlin –> Rome –> Athens –> Belgrade
- Reykjavik –> London –> Berlin –> Rome –> Athens –> Moscow –> Belgrade
Each of these paths end in Belgrade, but they all have different values. We can use Dijkstra’s algorithm to find the path with the lowest total value.
Dijkstra’s Algorithm: Step-by-Step Explanation
Before diving into the code, let’s start with a high-level illustration of Dijkstra’s algorithm.
First, we initialize the algorithm as follows:
- We set Reykjavik as the starting node.
- We set the distances between Reykjavik and all other cities to infinity, except for the distance between Reykjavik and itself, which we set to 0.
After that, we iteratively execute the following steps:
- We choose the node with the smallest value as the “current node” and visit all of its neighboring nodes. As we visit each neighbor, we update their tentative distance from the starting node.
- Once we visit all of the current node’s neighbors and update their distances, we mark the current node as “visited.” Marking a node as “visited” means that we’ve arrived at its final cost.
- We go back to step one. The algorithm loops until it visits all the nodes in the graph.
In our example, we start by marking Reykjavik as the “current node” since its value is 0. We proceed by visiting Reykjavik’s two neighboring nodes: London and Oslo. At the beginning of the algorithm, their values are set to infinity, but as we visit the nodes, we update the value for London to 4, and Oslo to 5.
We then mark Reykjavik as “visited.” We know that its final cost is zero, and we don’t need to visit it again. We continue with the next node with the lowest value, which is London.
We visit all of London’s neighboring nodes which we haven’t marked as “visited.” London’s neighbors are Reykjavik and Berlin, but we ignore Reykjavik because we’ve already visited it. Instead, we update Berlin’s value by adding the value of the edge connecting London and Berlin (3) to the value of London (4), which gives us a value of 7.
We mark London as visited and choose the next node: Oslo. We visit Oslo’s neighbors and update their values. It turns out that we can better reach Berlin through Oslo (with a value of 6) than through London, so we update its value accordingly. We also update the current value of Moscow from infinity to 8.
We mark Oslo as “visited” and update its final value to 5. Between Berlin and Moscow, we choose Berlin as the next node because its value (6) is lower than Moscow’s (8). We proceed as before: We visit Rome and Belgrade and update their tentative values, before marking Berlin as “visited” and moving on to the next city.
Note that we’ve already found a path from Reykjavik to Belgrade with a value of 15! But is it the best one?
Ultimately, it’s not. We’ll skip the rest of the steps, but you get the drill. The best path turns out to be Reykjavik –> Oslo –> Berlin –> Rome –> Athens –> Belgrade, with a value of 11.
Now, let’s see how we would implement this in Python code.
Dijkstra’s Algorithm in Python
- The Graph Class
First, we’ll create the Graph class. This class does not cover any of the Dijkstra algorithm’s logic, but it will make the implementation of the algorithm more succinct.
We’ll implement the graph as a Python dictionary. The dictionary’s keys will correspond to the cities and its values will correspond to dictionaries that record the distances to other cities in the graph.
import sys
class Graph(object):
def __init__(self, nodes, init_graph):
self.nodes = nodes
self.graph = self.construct_graph(nodes, init_graph)
def construct_graph(self, nodes, init_graph):
'''
This method makes sure that the graph is symmetrical. In other words, if there's a path from node A to B with a value V, there needs to be a path from node B to node A with a value V.
'''
graph = {}
for node in nodes:
graph[node] = {}
graph.update(init_graph)
for node, edges in graph.items():
for adjacent_node, value in edges.items():
if graph[adjacent_node].get(node, False) == False:
graph[adjacent_node][node] = value
return graph
def get_nodes(self):
"Returns the nodes of the graph."
return self.nodes
def get_outgoing_edges(self, node):
"Returns the neighbors of a node."
connections = []
for out_node in self.nodes:
if self.graph[node].get(out_node, False) != False:
connections.append(out_node)
return connections
def value(self, node1, node2):
"Returns the value of an edge between two nodes."
return self.graph[node1][node2]
2. The Dijkstra Algorithm
Next, we’ll implement the Dijkstra algorithm. We’ll start by defining the function.
def dijkstra_algorithm(graph, start_node):
The function takes two arguments: graph and start_node. graph is an instance of the Graph class that we created in the previous step, whereas start_node is the node from which we’ll start the calculations. We’ll call the get_nodes() method to initialize the list of uninvited nodes:
unvisited_nodes = list(graph.get_nodes())
Next, we’ll create two dicts, shortest_path and previous_nodes:
shortest_path will store the best-known cost of visiting each city in the graph starting from the start_node. In the beginning, the cost starts at infinity, but we’ll update the values as we move along the graph.
previous_nodes will store the trajectory of the current best known path for each node. For example, if we know the best way to Berlin to be via Oslo, previous_nodes["Berlin"] will return “Oslo”, and previous_nodes["Oslo"] will return “Reykjavik.” We’ll use this dictionary to backtrace the shortest path.
shortest_path = {}
previous_nodes = {}
# We'll use max_value to initialize the "infinity" value of the unvisited nodes
max_value = sys.maxsize
for node in unvisited_nodes:
shortest_path[node] = max_value
# However, we initialize the starting node's value with 0
shortest_path[start_node] = 0
Now we can start the algorithm. Remember that Dijkstra’s algorithm executes until it visits all the nodes in a graph, so we’ll represent this as a condition for exiting the while-loop.
while unvisited_nodes:
Now, the algorithm can start visiting the nodes. The code block below first instructs the algorithm to find the node with the lowest value.
current_min_node = None
for node in unvisited_nodes: # Iterate over the nodes
if current_min_node == None:
current_min_node = node
elif shortest_path[node] < shortest_path[current_min_node]:
current_min_node = node
Once that’s done, the algorithm visits all node’s neighbors that are still unvisited. If the new path to the neighbor is better than the current best path, the algorithm makes adjustments in the shortest_path and previous_nodes dictionaries.
# The code block below retrieves the current node's neighbors and updates their distances
neighbors = graph.get_outgoing_edges(current_min_node)
for neighbor in neighbors:
tentative_value = shortest_path[current_min_node] + graph.value(current_min_node, neighbor)
if tentative_value < shortest_path[neighbor]:
shortest_path[neighbor] = tentative_value
# We also update the best path to the current node
previous_nodes[neighbor] = current_min_node
After visiting all of its neighbors, we can mark the current node as “visited”:
unvisited_nodes.remove(current_min_node
At last, we can return the two dictionaries:
return previous_nodes, shortest_path
3.A Helper Function
Lastly, we need to create a function that prints out the results. This function will take the two dictionaries returned by the dijskstra_algorithm function, as well as the names of the beginning and target nodes. It’ll use the two dictionaries to find the best path and calculate the path’s score.
def print_result(previous_nodes, shortest_path, start_node, target_node):
path = []
node = target_node
while node != start_node:
path.append(node)
node = previous_nodes[node]
# Add the start node manually
path.append(start_node)
print("We found the following best path with a value of {}.".format(shortest_path[target_node]))
print(" -> ".join(reversed(path)))
The Algorithm in Action
Now, let’s see the algorithm in action. We’ll manually initialize the nodes and their edges.
nodes = ["Reykjavik", "Oslo", "Moscow", "London", "Rome", "Berlin", "Belgrade", "Athens"]
init_graph = {}
for node in nodes:
init_graph[node] = {}
init_graph["Reykjavik"]["Oslo"] = 5
init_graph["Reykjavik"]["London"] = 4
init_graph["Oslo"]["Berlin"] = 1
init_graph["Oslo"]["Moscow"] = 3
init_graph["Moscow"]["Belgrade"] = 5
init_graph["Moscow"]["Athens"] = 4
init_graph["Athens"]["Belgrade"] = 1
init_graph["Rome"]["Berlin"] = 2
init_graph["Rome"]["Athens"] = 2
We’ll use these values to create an object of the Graph class.
grapWith our graph fully constructed, we can pass it to the dijkstra_algorithm() functionh = Graph(nodes, init_graph)
previous_nodes, shortest_path = dijkstra_algorithm(graph=graph, start_node="Reykjavik")
And now let’s print out the results:
print_result(previous_nodes, shortest_path, start_node="Reykjavik", target_node="Belgrade")
We found the following best path with a value of 11.
Reykjavik -> Oslo -> Berlin -> Rome -> Athens -> Belgrade
And that’s it! Feel free to play around with the code. For example, you could add more nodes to the graph, tweak the edges’ values, or choose different starting and ending cities.
Keep Learning Python with Udacity
In this article, we provided a hands-on explanation of Dijkstra’s algorithm before showing an implementation in Python. Although Dijkstra’s algorithm is conceptually simple, it’s powerful enough to be employed in many interesting applications.
Looking to continue learning Python?
Check out our Introduction to Programming Nanodegree program. You’ll learn the foundations and work towards a career in fields like software development, machine learning, or data science!
Comments
Post a Comment