Dijkstra Algorithm – Part IV

QuantInsti

Contributor:
QuantInsti
Visit: QuantInsti

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.

Dijkstra Algorithm

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/

Disclosure: Interactive Brokers

Information posted on IBKR Traders’ Insight that is provided by third-parties and not by Interactive Brokers does NOT constitute a recommendation by Interactive Brokers that you should contract for the services of that third party. Third-party participants who contribute to IBKR Traders’ Insight are independent of Interactive Brokers and Interactive Brokers does not make any representations or warranties concerning the services offered, their past or future performance, or the accuracy of the information provided by the third party. Past performance is no guarantee of future results.

This material is from QuantInsti and is being posted with permission from QuantInsti. The views expressed in this material are solely those of the author and/or QuantInsti and IBKR is not endorsing or recommending any investment or trading discussed in the material. This material is not and should not be construed as an offer to sell or the solicitation of an offer to buy any security. To the extent that this material discusses general market activity, industry or sector trends or other broad based economic or political conditions, it should not be construed as research or investment advice. To the extent that it includes references to specific securities, commodities, currencies, or other instruments, those references do not constitute a recommendation to buy, sell or hold such security. This material does not and is not intended to take into account the particular financial conditions, investment objectives or requirements of individual customers. Before acting on this material, you should consider whether it is suitable for your particular circumstances and, as necessary, seek professional advice.

In accordance with EU regulation: The statements in this document shall not be considered as an objective or independent explanation of the matters. Please note that this document (a) has not been prepared in accordance with legal requirements designed to promote the independence of investment research, and (b) is not subject to any prohibition on dealing ahead of the dissemination or publication of investment research.

Any trading symbols displayed are for illustrative purposes only and are not intended to portray recommendations.