Dijkstra Algorithm – Part IV

See Part I for an overview of Dijkstra algorithm, Part II for pseudo code of Dijkstra algorithm and Part III for comparison with other algorithms .

How to find the shortest path using the Dijkstra algorithm?

In the following example, we will use the Dijkstra algorithm implemented in the Dijkstra library. However, we are not going to install the library in our development environment, but we will copy and use the code of the two necessary classes directly in order to be able to analyse the algorithm.

Note that the Dijkstra algorithm is implemented in other python modules as the Dijkstra from scipy.sparse.csgraph library.

The class ‘DijkstraSPF’ inherits from ‘​​AbstractDijkstraSPF’ and has two methods get_adjacent_nodes and get_edge_weight.

The __init__ function from ‘​​AbstractDijkstraSPF’ class has the Dijkstra algorithm as we have seen in the previous pseudocode.

The Graph class just has two methods to deal with a graph.

Let’s try the shortest path from A to E. As we can see, the straight path has a weight of 15, however, if we go through the nodes A-B (6), B-C(1), C-D(1) and D-E(4) that adds up to a total weight of 12, which means that this path, despite having more nodes, has a lower cost.

Example – The shortest path using the Dijkstra algorithm

The below classes are extracted from the Dijkstra library on GitHub.

import math

class AbstractDijkstraSPF(object):

    """ Dijkstra's shortest path algorithm, abstract class. """

    def __init__(self, G, s):
        """ Calculate shortest path from s to other nodes in G. """
        self.__dist = dist = dict()
        self.__prev = prev = dict()
        visited = set()
        queue = set()

        dist[s] = 0
        prev[s] = s
        queue.add(s)

        while queue:
            u = min(queue, key=dist.get)
            for v in self.get_adjacent_nodes(G, u):
                if v in visited:
                    continue
                alt = self.get_distance(u) + self.get_edge_weight(G, u, v)
                if alt < self.get_distance(v):
                    dist[v] = alt
                    prev[v] = u
                    queue.add(v)
            queue.remove(u)
            visited.add(u)

    @staticmethod
    def get_adjacent_nodes(G, u):
        raise NotImplementedError()

    @staticmethod
    def get_edge_weight(G, u, v):
        raise NotImplementedError()

    def get_distance(self, u):
        """ Return the length of shortest path from s to u. """
        return self.__dist.get(u, math.inf)

    def get_path(self, v):
        """ Return the shortest path to v. """
        path = [v]
        while self.__prev[v] != v:
            v = self.__prev[v]
            path.append(v)
        return path[::-1]

class DijkstraSPF(AbstractDijkstraSPF):

    @staticmethod
    def get_adjacent_nodes(G, u):
        return G.get_adjacent_nodes(u)

    @staticmethod
    def get_edge_weight(G, u, v):
        return G.get_edge_weight(u, v)

Importing math.py hosted with ❤ by GitHub

.

import random
from io import StringIO

class Graph(object):

    """ Directed, acyclic graph with edge weights.

    Graph can be constructed two different ways. Option 1 is to create an empty
    graph and add edges using added≥(u,w,v) method. For example, to
    create graph G connecting node 0 to node 1 with edge weight 5, and node 1
    to node 2 with edge weight 3, i.e.

           5      3
        0 ---> 1 ---> 2

    >>> G = Graph()
    >>> G.add_edge(0, 1, 5)
    >>> G.add_edge(1, 2, 3)

    Another option is to pass adjacency list and edge weights directly as
    dictionaries. The same example with that way is constructed as:

    >>> adjacency_list = {0: 1, 1: 2}
    >>> edge_weights = {(0, 1): 5, (1, 2): 3}
    >>> G = Graph(adjacency_list, edge_weights)

    """

    def __init__(self, adjacency_list=dict(), edge_weights=dict()):
        self.__adjacency_list = adjacency_list.copy()
        self.__edge_weights = edge_weights.copy()

    def add_edge(self, u, v, w):
        """ Add a new edge u -> v to graph with edge weight w. """
        self.__edge_weights[u, v] = w
        if u not in self.__adjacency_list:
            self.__adjacency_list[u] = set()
        self.__adjacency_list[u].add(v)

    def get_edge_weight(self, u, v):
        """ Get edge weight of edge between u and v. """
        return self.__edge_weights[u, v]

    def get_adjacent_nodes(self, u):
        """ Get nodes adjacent to u. """
        return self.__adjacency_list.get(u, set())

    def get_number_of_nodes(self):
        """ Return the total number of nodes in graph. """
        return len(self.__adjacency_list)

    def get_nodes(self):
        """ Return all nodes in this graph. """
        return self.__adjacency_list.keys()

    def __str__(self):
        io = StringIO()
        N = self.get_number_of_nodes()
        print("Directed, acyclic graph with %d nodes" % N, file=io)
        for u in self.get_nodes():
            adj = self.get_adjacent_nodes(u)
            print("Node %s: connected to %d nodes" % (u, len(adj)), file=io)
        return io.getvalue()

Importing random.py hosted with ❤ by GitHub

# If we install the dijkstra library, we can import the classes as usual.
# from Dijkstra import DijkstraSPF, Graph

Let’s create a simple graph to test the Dijkstra shortest path algorithm.

Let’s try the shortest path from A to E. As we can see, the direct path has a weight of 15, however, if we go through the nodes A-B (6), B-C(1), C-D(1) and D-E(4) that adds up to a total weight of 12, which means that this path, despite having more nodes, has a lower cost.

A, B, C, D, E = nodes = list("ABCDE")

graph = Graph()
graph.add_edge(A, B, 6)
graph.add_edge(A, E, 15)
graph.add_edge(B, C, 1)
graph.add_edge(C, D, 1)
graph.add_edge(D, E, 4)

dijkstra = DijkstraSPF(graph, A)

print("%-5s %-5s" % ("label", "distance"))
for u in nodes:
    print("%-5s %8f" % (u, dijkstra.get_distance(u)))

print("\nShortest path:")
print(" -> ".join(dijkstra.get_path(E)))

Simple graph Dijkstra's algorithm.py hosted with ❤ by GitHub

label distance
A     0.000000
B     6.000000
C     7.000000
D     8.000000
E     12.000000

Shortest path:
A -> B -> C -> D -> E

If we change the weight of segment [A, E] from 15 to 10, the algorithm has a direct path to the node E.

A, B, C, D, E = nodes = list("ABCDE")

graph = Graph()
graph.add_edge(A, B, 6)
graph.add_edge(A, E, 10)
graph.add_edge(B, C, 1)
graph.add_edge(C, D, 1)
graph.add_edge(D, E, 4)

dijkstra = DijkstraSPF(graph, A)

print("\nShortest path:")
print(" -> ".join(dijkstra.get_path(E)))

Nodes list.py hosted with ❤ by GitHub

Shortest path:
A -> E

As we can see, Dijkstra’s greedy algorithm is an optimal solution for finding shortest paths in a directed graph. However, it is not a valid algorithm for arbitrage since, having to normalise the prices to a logarithmic scale, we can obtain negative values for the weights. With the Dijkstra algorithm we would obtain infinite cycles, for which the Bellman-Ford algorithm is used.

Stay tuned for the next installment in which Mario Pisa will explain why the Dijkstra algorithm fails for negative weights

Visit QuantInsti for additional insight on this topic: https://blog.quantinsti.com/dijkstra-algorithm/