You can download the PDF file of the presentation here. Also, watch the presentation as a Gif here:
What is Dijkstra’s Algorithm?
Dijkstra’s algorithm solves the single-source shortest path (SSSP) problem. Generally, it enables finding the shortest route between two vertices in a graph. Its author is dr. Edsger W. Dijkstra, a pioneering contributor to computer science.
Dijkstra’s original algorithm is an uninformed greedy algorithm. Although it uses information in a form of weights of the edges, these weights are exact and inherent to the network, so no heuristic estimation function is used. In a most common example, Dijkstra’s algorithm finds the shortest path between any two cities in a graph.
What is Its Purpose?
Common applications of Dijkstra’s algorithm are in domains of optimal pathfinding for various distribution networks, such as oil, gas, electricity, road, or computer networks. Computer network equipment employs Dijkstra’s algorithm as a decision-making algorithm for optimal packet routing between network nodes (see the Open-Shortest Path First protocol).
Algorithm Overview: How Does Dijkstra Work?
Dijkstra’s algorithm assumes the cost of all vertices except the starting one as infinite. It sets the cost of the starting vertex to 0 and updates the costs of all adjoining, unexplored vertices, according to the weights (distances) associated with the connecting edges. After being visited, each adjoining vertex is added to the priority queue. Finally, the starting vertex is marked as explored and does not participate in any further algorithm calculations.
In each following iteration, the vertex with the lowest cost is taken out of the priority queue and its exploration starts by visiting and conditionally updating all adjoining, non-explored vertices. The update operation implies two steps: assignment of the lower cost to the adjoining node and association with the ancestor vertex for later reconstruction of the shortest path.
The update condition is determined by comparing each adjoining vertex’s current cost with its new, potentially lower cost. Its new cost is calculated as the cost of the vertex being explored + the weight of the adjoining edge (the between the vertex being explored and the adjoining vertex).
If the current cost of the adjoining vertex is still lower than the potential new cost, the vertex will not be updated. Otherwise, it will assume the new cost (its cost will decrease) and the vertex in focus will become its ancestor vertex. Vertex cost reduction is also referred to as a relaxation procedure.
After visiting and conditionally updating all the adjoining, non-explored vertices, the vertex being explored will be marked as explored and will not participate in any further algorithm calculations. The described process continues until there are no unexplored vertices left in the priority queue.
When the algorithm ends, all vertices are assigned with the lowest possible costs, and the traversal algorithm yields the shortest possible path between the starting and target vertices. For comparison with the previously described best-first search algorithm: if its heuristic function would give the same relative cost for all vertices as the Dijkstra’s algorithm, it would also traverse the vertices in the same order and yield the same shortest path.
What Are Properties of Dijkstra?
Dijkstra’s algorithm doesn’t use a heuristic function and doesn’t estimate the costs of the graph’s vertices. Instead, it relies on the exact information represented by the edge’s weights. As the initial costs of non-starting vertices are set to infinity, the algorithm successively lowers their costs until they reach their minimum cost.
This behavior yields its optimality property: minimum costs assigned to vertices enable the algorithm to always find the shortest path between the starting vertex and any other vertex in the graph. As the shortest paths always start from the starting vertex, the algorithm is attributed as the “single-source” algorithm.
Besides being optimal, the algorithm is also complete, i.e., it will always take a finite time to find a solution.
However, Dijkstra’s algorithm cannot handle edges with negative weights.
Implementation Python Dijkstra
The implementation of Dijkstra’s algorithm is achieved by function dijkstra() and a modification of the underlying class Graph.
The dijkstra() function takes three parameters:
- The
graphparameter takes an initialized Graph object (see the blog on the breadth-first search algorithm, the section on graphs). - The
start_vertexparameter takes the starting vertex, which we choose freely (remember, a graph is not a tree, there is no absolute root). - The
targetparameter is the entity we want to find in the graph, enclosed in a vertex.
For a better understanding of the algorithm and its implementation, each step is precisely described in the code below.
As we introduced several changes to the Graph class, the most practical approach is to show the entire class:
class Graph:
def __init__(self, directed=False):
self._outgoing = {}
# If the graph is undirected, 'self._outgoing'
# is the universal storage.
self._incoming = {} if directed else self._outgoing
# If the graph is directed, the 'self._incoming'
# dictionary differs from the 'self._outgoing'.
def is_directed(self):
return self._incoming is not self._outgoing
# The function returns a generator of incoming
# or outgoing (default) edges of a vertex.
def adjacent_edges(self, vertex, outgoing=True):
# References the corresponding outer dictionary
# (dictionary of dictionaries)
adj_edges = self._outgoing if outgoing else self._incoming
# Access each of the edges for this endpoint vertex.
for edge in adj_edges[vertex].values():
yield edge
def add_vertex(self, entity=None, h=None):
# Constructs a new vertex from the entity.
vertex = self.Vertex(entity, h)
# The vertex becomes a key in the outer dictionary,
# but the value is an internal dictionary (as we model
# both dimensions for each edge: origin and destination).
# e.g. {vertex_1a:{vertex_b:edge_a_b}, vertex_b:{vertex_c:edge_b_c}}.
self._outgoing[vertex] = {}
if self.is_directed():
self._incoming[vertex] = {}
def add_edge(self, origin, destination, weight=None):
# Constructs a new edge from the vertices.
edge = self.Edge(origin, destination, weight)
# Adds the edge to the dictionary (dictionaries are
# the same if the graph is undirected). The outer key
# represents the origin, i.e. the component 'a' of
# the edge-defining pair (a, b). The inner key stands
# for the component 'b' of the edge-defining pair (a, b).
self._outgoing[origin][destination] = edge
# Even if the graph is undirected, each edge has to
# be added twice, i.e. once for each of its endpoints.
self._incoming[destination][origin] = edge
def vertices(self):
return self._outgoing.keys()
def edges(self):
# All the edges are collected into a set.
result = set()
for inner_dict in self._outgoing.values():
result.update(inner_dict.values())
return result
class Vertex:
__slots__ = '_entity', '_h'
def __init__(self, entity, h=None):
self.entity = entity
self.h = h
# The real-world entity is represented by the Vertex object.
@property
def entity(self):
return self._entity
@entity.setter
def entity(self, entity):
self._entity = entity
# The real-world entity has a cost of h.
@property
def h(self):
return self._h
@h.setter
def h(self, h):
self._h = h
# We have to implement __hash__ to use the object as a dictionary key.
def __hash__(self):
return hash(id(self))
def __lt__(self, other):
if self.h is None:
return False
elif other.h is None:
return True
else:
return self.h < other.h
class Edge:
__slots__ = '_origin', '_destination', '_weight'
def __init__(self, origin, destination, weight=None):
self._origin = origin
self._destination = destination
self._weight = weight
def endpoints(self):
return self._origin, self._destination
# Returns the other component of the edge-defining pair (a, b)
# for a given component a or b, respectively.
def opposite(self, vertex):
return self._destination if self._origin is vertex \
else self._origin
# Returns the weight of the edge.
@property
def weight(self):
return self._weight
# Sets the weight of the edge
@weight.setter
def weight(self, weight):
self._weight = weight
def __hash__(self):
return hash((self._origin, self._destination))
A significant difference to the previous version of the Graph class is the introduction of the property decorator and the weight attribute, as highlighted in the code.
With these changes in place, implementation of the core function, dijkstra() is:
from graph import Graph
from queue import PriorityQueue
def dijkstra(graph, start_vertex, target):
# Create the priority queue for open vertices.
vertices_pq = PriorityQueue()
# Initialize the starting vertex to cost 0.
start_vertex.h = 0
# Adds the start vertex to the priority queue.
print(f'Visiting/queueing vertex {start_vertex.entity}')
vertices_pq.put(start_vertex)
print('Prioritized vertices (v, h(v)):',
*((vert.entity, vert.h) for vert in vertices_pq.queue), end=2 * '\n')
# The starting vertex is visited first and has no leading edges.
# If we did not put it into 'visited' in the first iteration,
# it would end up in 'visited' during the second iteration, pointed to
# by one of its children vertices as a previously unvisited vertex.
visited[start_vertex] = None
# Loops until the priority list gets empty.
while not vertices_pq.empty():
# Gets the vertex with the lowest cost.
vertex = vertices_pq.get()
# If the vertex being explored is a target vertex, ends the algorithm.
print(f'Exploring vertex {vertex.entity}')
if vertex.entity == target:
return vertex
# Examines each non-visited adjoining edge/vertex.
for edge in graph.adjacent_edges(vertex):
# Gets the second endpoint.
v_2nd_endpoint = edge.opposite(vertex)
# Skips the explored vertices.
if v_2nd_endpoint in explored:
continue
# Checks if the endpoint has a cost and is the cost the cheapest one.
if v_2nd_endpoint.h is None or vertex.h + ed