Dijkstra's Algorithm in Python

Dijkstra’s algorithm can be defined as a greedy algorithm that can be utilized to find out the shortest distance possible from a source vertex to any other possible vertex that exists in a weighted graph, provided that the vertex is reachable from the source vertex.

This tutorial discusses how to implement Dijkstra’s algorithm for finding the shortest path in Python.

As mentioned above, Dijkstra’s algorithm is greedy. A greedy algorithm can be defined as an algorithmic paradigm that focuses on building up a piece-by-piece solution to the given problem, choosing the most beneficial option then.

How Dijkstra’s algorithm works is as follows.

• Given a couple of unvisited vertices, select the vertex with the smallest distance from the source and visit it.
• The distance for each neighboring is then updated. The same is done for the visited vertex, which has a current distance greater than the sum and the weight of the given edge between them.
• Steps 1 and 2 need to be repeated until there are no unvisited vertices.

Dijkstra’s algorithm holds a resemblance to Prim’s Minimum Spanning Tree algorithm, another Greedy algorithm, as both of them need the generation of an SPT(shortest path tree), taking the source as the root of the tree.

The following code uses Dijkstra’s algorithm for finding the shortest path in Python.

import sys


class Graph:
    def __init__(self, vertx):
        self.V = vertx
        self.graph = [[0 for column in range(vertx)] for row in range(vertx)]

    def pSol(self, dist):
        print("Distance of vertex from source")
        for node in range(self.V):
            print(node, "t", dist[node])

    def minDistance(self, dist, sptSet):

        min = sys.maxsize

        for v in range(self.V):
            if dist[v] < min and sptSet[v] == False:
                min = dist[v]
                min_index = v

        return min_index

    def dijk(self, source):

        dist = [sys.maxsize] * self.V
        dist[source] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            u = self.minDistance(dist, sptSet)

            sptSet[u] = True

            for v in range(self.V):
                if (
                    self.graph[u][v] > 0
                    and sptSet[v] == False
                    and dist[v] > dist[u] + self.graph[u][v]
                ):
                    dist[v] = dist[u] + self.graph[u][v]

        self.pSol(dist)


f = Graph(9)
f.graph = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0],
]

f.dijk(0)

The above code provides the following output:

Distance of vertex from source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14

Dijkstra’s algorithm is very similar to the Depth First Search algorithm, although both of these algorithms do not precisely exist for the same purpose.

The only significant difference between Depth First Search and Dijkstra’s algorithm is that the former works slower than the latter as the Depth First Search(DFS) algorithm uses the stack technique. On the other hand, Dijkstra’s algorithm makes use of the comparatively slower heap technique.