# Dijkstra Algorithm – Part IV

Articles From: QuantInsti
Website: 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.

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

while queue:
u = min(queue, key=dist.get)
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.remove(u)

@staticmethod
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

@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
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()

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}

"""

self.__edge_weights = edge_weights.copy()

""" Add a new edge u -> v to graph with edge weight w. """
self.__edge_weights[u, v] = w

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

""" Get nodes adjacent to u. """

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

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

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():
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()

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()

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 Campus that is provided by third-parties does NOT constitute a recommendation that you should contract for the services of that third party. Third-party participants who contribute to IBKR Campus 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 its permission. The views expressed in this material are solely those of the author and/or QuantInsti and Interactive Brokers 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 buy or sell any security. It should not be construed as research or investment advice or a recommendation to buy, sell or hold any security or commodity. 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.