Implement Dijkstra Algorithm using Python- Single source path

Dijkstra Algorithm
Spread the love

Dijkstra algorithm is used to find the shortest paths between nodes in a graph. Given a source node in the graph, the algorithm finds the shortest path between that node and every other. In this tutorial, we are going to see how to implement the Dijkstra algorithm using python.

In the BFS traversal algorithm, we have a constant that our graph’s edges should be the same cost. But Dijkstra algorithm the edges should not be the mandatory same cost. The drawback of the Dijkstra algorithm is if the cost of the edge is negative then this algorithm may or may not work. To solve this issue we can use another algorithm that is the Bellman-Ford algorithm.

Read More: Detecting Cycle in a Graph using DFS Algorithm in Python

Let’s see the algorithm of the Dijkstra code.

Algorithm of Dijkstra

  • Maintain a set of pressed node
  • Assign all nodes with distance value is equal to infinite except the source node. Assign zero in source node.
  • Repeat the following steps. (Unless the all vertices are incuded)
    • Pick the min value of vertics which is not already pressed.
    • Include the seleted node in the pressed set
    • Update the all adjacent node distaces if the new distance is greater than old distance else skip.

Let’s see this graph. In this tutorial, we will implement this graph that is an undirected graph, and also find the shortest path.

Well, let’s make this graph into an adjacency list in python. To do that I will use python dictionary data structure. Let’s see the pieces of code.

graph = {
    "A": {"B": 2, "C": 4},
    "B": {"A": 2, "C": 3, "D": 8},
    "C": {"A": 4, "B": 3, "D": 2, "E": 5},
    "D": {"B": 8, "C": 2, "F": 22, "E": 11},
    "E": {"C": 5, "D": 11, "F": 1},
    "F": {"D": 22, "E": 1},
}

Well, to implement this algorithm we need a built-in module that is sys. Also, we need a heap module. Let’s import these modules.

import sys
from heapq import heapify, heappush, heappop

Now see the code of the Dijkstra algorithm’s function. I will explain you later.

def dijkstra(graph, source, destination):
    inf = sys.maxsize
    node_data = {}
    for node in graph.keys():
        node_data[node] = {'cost': inf, 'pred': []}

    node_data[source]['cost'] = 0
    visited = []
    temp = source

    for i in range((len(graph.keys())-1)):
        if temp not in visited:
            visited.append(temp)
            min_heap = []
            for j in graph[temp]:
                if j not in visited:
                    cost = node_data[temp]['cost'] + graph[temp][j]
                    if cost < node_data[j]['cost']:
                        node_data[j]['cost'] = cost
                        node_data[j]['pred'] = node_data[temp]['pred'] + \
                            list(temp)
                    heappush(min_heap, (node_data[j]['cost'], j))
        heapify(min_heap)
        temp = min_heap[0][1]
        # print(temp)
        # return
    print("Sortest Distance : ", str(node_data[destination]['cost']))
    print("Sortest Path : ", str(
        node_data[destination]['pred'] + list(destination)))

Well, this function takes three parameters. There is the graph another one is the source node and the last one is the destination node. Inside this function, first I have taken two variables and then done initial tasks. The initial task is according to the algorithm is to set all vertices cost is equal to infinite and the predecessor of a node is an empty list. Then assign the source node into a temporary variable.

Well, now you have to execute a loop from zero to before the number of nodes. Inside the loop, first, you have to check the temporary node is visited or not. Then take a list for min-heap.

Now you have to execute another loop. Inside the loop, you have to check the unvisited neighbor. After then you have to calculate the cost. If the cost is greater than the neighbor node then reassign the cost value. Then push the neighbor into the heap as well cost. Finally, call the heapify function and reassign the temp value with the heap’s min value.

Now print the shortest distances as well the shortest path using the destination node.

Full Code



import sys
from heapq import heapify, heappush, heappop


def dijkstra(graph, source, destination):
    inf = sys.maxsize
    node_data = {}
    for node in graph.keys():
        node_data[node] = {'cost': inf, 'pred': []}

    node_data[source]['cost'] = 0
    visited = []
    temp = source

    for i in range((len(graph.keys())-1)):
        if temp not in visited:
            visited.append(temp)
            min_heap = []
            for j in graph[temp]:
                if j not in visited:
                    cost = node_data[temp]['cost'] + graph[temp][j]
                    if cost < node_data[j]['cost']:
                        node_data[j]['cost'] = cost
                        node_data[j]['pred'] = node_data[temp]['pred'] + \
                            list(temp)
                    heappush(min_heap, (node_data[j]['cost'], j))
        heapify(min_heap)
        temp = min_heap[0][1]
        # print(temp)
        # return
    print("Sortest Distance : ", str(node_data[destination]['cost']))
    print("Sortest Path : ", str(
        node_data[destination]['pred'] + list(destination)))


graph = {
    "A": {"B": 2, "C": 4},
    "B": {"A": 2, "C": 3, "D": 8},
    "C": {"A": 4, "B": 3, "D": 2, "E": 5},
    "D": {"B": 8, "C": 2, "F": 22, "E": 11},
    "E": {"C": 5, "D": 11, "F": 1},
    "F": {"D": 22, "E": 1},
}


source = "A"
destination = "E"
dijkstra(graph, source, destination)

Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m an Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://tutspack.com

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.