Shortest Paths Dijkstra Algorithm In Python

Since the dawn of time, humans have looked for methods that reduce costs and save both time and energy in every aspect of their lives. Achieving the same goals with the least cost has always been an important approach to survival for our ancestors. In this same perspective, and in order to satisfy this need for optimization that coexists in our modern societies, mathematicians developed several algorithms called 'Greedy algorithms’. As you can guess, the strategy adopted by those algorithms is to make greedy decisions at each node while selecting the next hop. Among those algorithms, Dijkstra has proved to be valuable especially in IT. It was developed by Edsger W. Dijkstra in 1956 and applied in many researches.

So, what is the shortest paths algorithm? What is the mathematical background of the Dijkstra algorithm (DA)? How can we conceive Dijkstra in python?

Shortest Path Algorithms (SPA)

Shortest paths algorithms put the light on numerous and large variety of problems. They aim to find out the paths of minimal weights among a variety of other possible paths. (A path is composed of  nodes and weighted links between those nodes) .

Different SPA has been conceived to solve various natures of graphs and inputs.

For example, for directed acyclic graphs

-Fig (a)  we recommend Topological Sorting (TS) method, while for general weighted graphs (containing both negative and positive values)  

-Fig (b)  we mostly use the Bellman-Ford algorithm.

But for positively weighted graphs –Fig(c)  we invite you to apply the Dijkstra algorithm.

Understanding the concepts of “the shortest paths algorithms” is essential to see clearly the theoretical and conceptual logic behind the Dijkstra algorithm. We have already mentioned that this family of algorithms has witnessed several modifications, during the time, to serve more specific and complex cases. For the sake of simplicity, the discussion of those algorithms will be restricted to the classical form of  SPA.

Here is a simplified example

Let’s suppose that you are traveling from your home ‘H’ to your work ‘W’ in your car, you will be passing by many cities. As it is a long ride, you decided to find out the shortest paths you can take from ‘H’ to 'W'.Consider ‘c’ the number of possible cities you will pass by where c>1, and T is a matrix in which we gather all the minimal distances between those cities(directly linked), so T(i,j) is the great-circle distance from city ‘i’ to city ‘j’.If there is no direct link between the two cities i and j, we can suppose that T(i,j)=∞ .So if the length of the shortest path between ‘H’ and ‘W’ is ∞ then there is no attainable way between the source and the destination.

∀ i,j ∈ {1..c }  -∞ ≤T(i,j)≤+∞ , but we can specify that for this particular example that ∀ i,j ∈ {1..c }  0≤T(i,j)≤+∞ because distances between cities are always positive. As you are starting at the departure point ‘H’, we suppose that ‘H’ has no predecessors directly linked to it.

So, the SPA will be applied to select the shortest path with the lowest value between home and work where this value equals the sum of hops that link directly cities on our map.

Dijkstra Algorithm

DA is one of most brilliant algorithms among SPA family.It is considered as a ‘heuristic and a greedy Algorithm’. As you can guess from this appellation ,it takes greedy decisions at each node to select the next hop it will take without considering upcoming nodes and links.

The DA imposes one condition : The graph must be positively weighted on all its edges, no negative values are allowed. It can be applied on cyclic ,acyclic,directed or undirected graphs.

‘H’is our starting point in this scenario.It’s  also called the single source vertex. ‘H’ will be illustrated by the red vertex 1 in the graph –Fig(d) while ‘W’ the destination point will be illustrated by the green vertex 6.

Let’s suppose that l(j) is the function that calculates the distance between ‘1’ and each city ‘j’ , L(H) = L(1) = 0 and L(j)=∞ where   j ∈ {2..c }  ,c=6

DA relies on the repetition of some operations until the wanted destination is reached. This is the reason why this algorithm is considered iterative.

While driving your car, you will avoid taking roads that are directly linked to unvisited cities with larger distances. So you will go to the closest city in metrics. Once you arrive at the next station, you need to update the status of the nodes (visited /unvisited) and also the distance values of adjacent vertices.

Here is an explanation of the steps used at each iteration:

While you didn’t reach your wanted destination and we still have unvisited vertices do:

1. Choose the next node N with the smallest distance to the source node (we have already mentioned that L(1)=0, so the algorithm will select N=‘1’ ( the source point) at the first iteration, but starting from the second iteration the closest node to the source will be selected.

2. Update the status of node N as been visited :

   This update can be done by using an initially empty set ‘U’ to which we add the visited nodes, in order, each time the algorithm selects one.

3. Update the distance values of neighboring nodes to N: 

   This update concerns each of N’s adjacent vertices ‘j’ that will be treated in the next step, with j ∈ {(1+u)..c } where u is the number of elements in the set ‘U’ which tells the number of the selected nodes.Set  l(j) as the new minimal distance value only      if  l(N)+T(N,j) < l(j) else no update is made for the adjacent node ‘j’

Implementation in Python

# Import the sys module in our program before running any functions
import sys

# The inputs of our algorithm
# Return to the graph Fig-d and build a matrix called distances to specify distances
# between directly related nodes and a matrix called nodes which specifies how nodes
# are related to each other. Both of these matrix are [c*c]

distances = [
    [0, 5, 17, 0, 20, 0],
    [0, 0, 0, 4, 0, 0],
    [0, 0, 2, 0, 0, 0],
    [0, 0, 0, 0, 0, 3],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0]
]

nodes = [
    [0, 1, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0]
]

# Decide which note will be visited among the Unvisited ones
def NextUp():
    global MinimDist
    Minim = -1
    # Select N node (explained in step 1)
    # c is the total number of nodes, in our example we have 6 nodes
    for v in range(c):
        if (Minim < 0 or (MinimDist[v][1] <= MinimDist[Minim][1]) and MinimDist[v][0] == 0):
            Minim = v
    return Minim

c = len(nodes[0])
# Update the status of node N as between visited
# figure out the distance from the source
# return to step (2) in the explanation
MinimDist = [[0, 0]]
for f in range(c - 1):
    MinimDist.append([0, sys.maxsize])
for vertex in range(c):
    # Select the next node (See step 2 in the explanation)
    Next = NextUp()
    for adjacent in range(c):
        # Make the sum to find out the new distance for the unvisitied adjacent vertices
        if nodes[Next][adjacent] == 1 and MinimDist[adjacent][0] == 0:
            nDist = MinimDist[Next][1] + distances[Next][adjacent]
            # Update the distance values of neighboring nodes to N
            # View step 3 in the explanation
            if MinimDist[adjacent][1] > nDist:
                MinimDist[adjacent][1] = nDist
    MinimDist[Next][0] = 1
f = 0
# Give the minimal distance from the you home to each City
for d in MinimDist:
    print("The shortest distance of", (1 + f), " from your home H is:", d[1])
    f = f + 1

created by Dora Boukari

Python code authorship protection

If you’re looking for a way to copyright your Python code, the Algo one-click solution is the best option for you. Algo provides developers a way to establish traceable authorship for their code or entire projects.
With Algo, a deposit transaction is instantly added to a blockchain-based repository service with public metadata, guaranteeing its immutability and the developer’s traceable authorship.