title dijkstra s algorithm for finding single source shortest path from scratch shubham malik references https en wikipedia orgwikidijkstra27salgorithm for storing the vertex set to retrieve node with the lowest distance based on min heap priority queue class constructor method examples priorityqueuetest priorityqueue priorityqueuetest cursize 0 priorityqueuetest array priorityqueuetest pos conditional boolean method to determine if the priority queue is empty or not examples priorityqueuetest priorityqueue priorityqueuetest isempty true priorityqueuetest insert2 a priorityqueuetest isempty false sorts the queue array so that the minimum element is root examples priorityqueuetest priorityqueue priorityqueuetest cursize 3 priorityqueuetest pos a 0 b 1 c 2 priorityqueuetest array 5 a 10 b 15 c priorityqueuetest minheapify0 traceback most recent call last typeerror list object is not callable priorityqueuetest array 5 a 10 b 15 c priorityqueuetest array 10 a 5 b 15 c priorityqueuetest minheapify0 traceback most recent call last typeerror list object is not callable priorityqueuetest array 10 a 5 b 15 c priorityqueuetest array 10 a 15 b 5 c priorityqueuetest minheapify0 traceback most recent call last typeerror list object is not callable priorityqueuetest array 10 a 15 b 5 c priorityqueuetest array 10 a 5 b priorityqueuetest cursize lenpriorityqueuetest array priorityqueuetest pos a 0 b 1 priorityqueuetest minheapify0 traceback most recent call last typeerror list object is not callable priorityqueuetest array 10 a 5 b inserts a node into the priority queue examples priorityqueuetest priorityqueue priorityqueuetest insert10 a priorityqueuetest array 10 a priorityqueuetest insert15 b priorityqueuetest array 10 a 15 b priorityqueuetest insert5 c priorityqueuetest array 5 c 10 a 15 b removes and returns the min element at top of priority queue examples priorityqueuetest priorityqueue priorityqueuetest array 10 a 15 b priorityqueuetest cursize lenpriorityqueuetest array priorityqueuetest pos a 0 b 1 priorityqueuetest insert5 c priorityqueuetest extractmin c priorityqueuetest array0 15 b returns the index of left child examples priorityqueuetest priorityqueue priorityqueuetest left0 1 priorityqueuetest left1 3 returns the index of right child examples priorityqueuetest priorityqueue priorityqueuetest right0 2 priorityqueuetest right1 4 returns the index of parent examples priorityqueuetest priorityqueue priorityqueuetest par1 0 priorityqueuetest par2 1 priorityqueuetest par4 2 swaps array elements at indices i and j update the pos examples priorityqueuetest priorityqueue priorityqueuetest array 10 a 15 b priorityqueuetest cursize lenpriorityqueuetest array priorityqueuetest pos a 0 b 1 priorityqueuetest swap0 1 priorityqueuetest array 15 b 10 a priorityqueuetest pos a 1 b 0 decrease the key value for a given tuple assuming the newd is at most oldd examples priorityqueuetest priorityqueue priorityqueuetest array 10 a 15 b priorityqueuetest cursize lenpriorityqueuetest array priorityqueuetest pos a 0 b 1 priorityqueuetest decreasekey10 a 5 priorityqueuetest array 5 a 15 b assuming the newd is atmost oldd graph class constructor examples graphtest graph1 graphtest numnodes 1 graphtest dist 0 graphtest par 1 graphtest adjlist to store the distance from source vertex add edge going from node u to v and v to u with weight w u w v v w u examples graphtest graph1 graphtest addedge1 2 1 graphtest addedge2 3 2 graphtest adjlist 1 2 1 2 1 1 3 2 3 2 2 check if u already in graph assuming undirected graph show the graph u vw examples graphtest graph1 graphtest addedge1 2 1 graphtest showgraph 1 21 2 11 graphtest addedge2 3 2 graphtest showgraph 1 21 2 11 32 3 22 dijkstra algorithm examples graphtest graph3 graphtest addedge0 1 2 graphtest addedge1 2 2 graphtest dijkstra0 distance from node 0 node 0 has distance 0 node 1 has distance 2 node 2 has distance 4 graphtest dist 0 2 4 graphtest graph2 graphtest addedge0 1 2 graphtest dijkstra0 distance from node 0 node 0 has distance 0 node 1 has distance 2 graphtest dist 0 2 graphtest graph3 graphtest addedge0 1 2 graphtest dijkstra0 distance from node 0 node 0 has distance 0 node 1 has distance 2 node 2 has distance 0 graphtest dist 0 2 0 graphtest graph3 graphtest addedge0 1 2 graphtest addedge1 2 2 graphtest addedge0 2 1 graphtest dijkstra0 distance from node 0 node 0 has distance 0 node 1 has distance 2 node 2 has distance 1 graphtest dist 0 2 1 graphtest graph4 graphtest addedge0 1 4 graphtest addedge1 2 2 graphtest addedge2 3 1 graphtest addedge0 2 3 graphtest dijkstra0 distance from node 0 node 0 has distance 0 node 1 has distance 4 node 2 has distance 3 node 3 has distance 4 graphtest dist 0 4 3 4 graphtest graph4 graphtest addedge0 1 4 graphtest addedge1 2 2 graphtest addedge2 3 1 graphtest addedge0 2 7 graphtest dijkstra0 distance from node 0 node 0 has distance 0 node 1 has distance 4 node 2 has distance 6 node 3 has distance 7 graphtest dist 0 4 6 7 flush old junk values in par src is the source node update the distance of all the neighbours of u and if their prev dist was infinity then push them in q show the shortest distances from src show the distances from src to all other nodes in a graph examples graphtest graph1 graphtest showdistances0 distance from node 0 node 0 has distance 0 shows the shortest path from src to dest warning use it after calling dijkstra examples graphtest graph4 graphtest addedge0 1 1 graphtest addedge1 2 2 graphtest addedge2 3 3 graphtest dijkstra0 distance from node 0 node 0 has distance 0 node 1 has distance 1 node 2 has distance 3 node 3 has distance 6 graphtest showpath0 3 doctest normalizewhitespace path to reach 3 from 0 0 1 2 3 total cost of path 6 backtracking from dest to src output 0 14 78 1 04 28 711 7 08 111 61 87 2 18 37 82 54 3 27 49 514 8 22 66 77 5 24 314 410 62 4 39 510 6 52 71 86 distance from node 0 node 0 has distance 0 node 1 has distance 4 node 2 has distance 12 node 3 has distance 19 node 4 has distance 21 node 5 has distance 11 node 6 has distance 9 node 7 has distance 8 node 8 has distance 14 path to reach 4 from 0 0 7 6 5 4 total cost of path 21 title dijkstra s algorithm for finding single source shortest path from scratch shubham malik references https en wikipedia org wiki dijkstra 27s_algorithm for storing the vertex set to retrieve node with the lowest distance based on min heap priority queue class constructor method examples priority_queue_test priorityqueue priority_queue_test cur_size 0 priority_queue_test array priority_queue_test pos to store the pos of node in array conditional boolean method to determine if the priority queue is empty or not examples priority_queue_test priorityqueue priority_queue_test is_empty true priority_queue_test insert 2 a priority_queue_test is_empty false sorts the queue array so that the minimum element is root examples priority_queue_test priorityqueue priority_queue_test cur_size 3 priority_queue_test pos a 0 b 1 c 2 priority_queue_test array 5 a 10 b 15 c priority_queue_test min_heapify 0 traceback most recent call last typeerror list object is not callable priority_queue_test array 5 a 10 b 15 c priority_queue_test array 10 a 5 b 15 c priority_queue_test min_heapify 0 traceback most recent call last typeerror list object is not callable priority_queue_test array 10 a 5 b 15 c priority_queue_test array 10 a 15 b 5 c priority_queue_test min_heapify 0 traceback most recent call last typeerror list object is not callable priority_queue_test array 10 a 15 b 5 c priority_queue_test array 10 a 5 b priority_queue_test cur_size len priority_queue_test array priority_queue_test pos a 0 b 1 priority_queue_test min_heapify 0 traceback most recent call last typeerror list object is not callable priority_queue_test array 10 a 5 b inserts a node into the priority queue examples priority_queue_test priorityqueue priority_queue_test insert 10 a priority_queue_test array 10 a priority_queue_test insert 15 b priority_queue_test array 10 a 15 b priority_queue_test insert 5 c priority_queue_test array 5 c 10 a 15 b removes and returns the min element at top of priority queue examples priority_queue_test priorityqueue priority_queue_test array 10 a 15 b priority_queue_test cur_size len priority_queue_test array priority_queue_test pos a 0 b 1 priority_queue_test insert 5 c priority_queue_test extract_min c priority_queue_test array 0 15 b returns the index of left child examples priority_queue_test priorityqueue priority_queue_test left 0 1 priority_queue_test left 1 3 returns the index of right child examples priority_queue_test priorityqueue priority_queue_test right 0 2 priority_queue_test right 1 4 returns the index of parent examples priority_queue_test priorityqueue priority_queue_test par 1 0 priority_queue_test par 2 1 priority_queue_test par 4 2 swaps array elements at indices i and j update the pos examples priority_queue_test priorityqueue priority_queue_test array 10 a 15 b priority_queue_test cur_size len priority_queue_test array priority_queue_test pos a 0 b 1 priority_queue_test swap 0 1 priority_queue_test array 15 b 10 a priority_queue_test pos a 1 b 0 decrease the key value for a given tuple assuming the new_d is at most old_d examples priority_queue_test priorityqueue priority_queue_test array 10 a 15 b priority_queue_test cur_size len priority_queue_test array priority_queue_test pos a 0 b 1 priority_queue_test decrease_key 10 a 5 priority_queue_test array 5 a 15 b assuming the new_d is atmost old_d graph class constructor examples graph_test graph 1 graph_test num_nodes 1 graph_test dist 0 graph_test par 1 graph_test adjlist to store graph u v w number of nodes in graph to store the distance from source vertex to store the path add edge going from node u to v and v to u with weight w u w v v w u examples graph_test graph 1 graph_test add_edge 1 2 1 graph_test add_edge 2 3 2 graph_test adjlist 1 2 1 2 1 1 3 2 3 2 2 check if u already in graph assuming undirected graph show the graph u v w examples graph_test graph 1 graph_test add_edge 1 2 1 graph_test show_graph 1 2 1 2 1 1 graph_test add_edge 2 3 2 graph_test show_graph 1 2 1 2 1 1 3 2 3 2 2 dijkstra algorithm examples graph_test graph 3 graph_test add_edge 0 1 2 graph_test add_edge 1 2 2 graph_test dijkstra 0 distance from node 0 node 0 has distance 0 node 1 has distance 2 node 2 has distance 4 graph_test dist 0 2 4 graph_test graph 2 graph_test add_edge 0 1 2 graph_test dijkstra 0 distance from node 0 node 0 has distance 0 node 1 has distance 2 graph_test dist 0 2 graph_test graph 3 graph_test add_edge 0 1 2 graph_test dijkstra 0 distance from node 0 node 0 has distance 0 node 1 has distance 2 node 2 has distance 0 graph_test dist 0 2 0 graph_test graph 3 graph_test add_edge 0 1 2 graph_test add_edge 1 2 2 graph_test add_edge 0 2 1 graph_test dijkstra 0 distance from node 0 node 0 has distance 0 node 1 has distance 2 node 2 has distance 1 graph_test dist 0 2 1 graph_test graph 4 graph_test add_edge 0 1 4 graph_test add_edge 1 2 2 graph_test add_edge 2 3 1 graph_test add_edge 0 2 3 graph_test dijkstra 0 distance from node 0 node 0 has distance 0 node 1 has distance 4 node 2 has distance 3 node 3 has distance 4 graph_test dist 0 4 3 4 graph_test graph 4 graph_test add_edge 0 1 4 graph_test add_edge 1 2 2 graph_test add_edge 2 3 1 graph_test add_edge 0 2 7 graph_test dijkstra 0 distance from node 0 node 0 has distance 0 node 1 has distance 4 node 2 has distance 6 node 3 has distance 7 graph_test dist 0 4 6 7 flush old junk values in par src is the source node dist from src node infinity returns node with the min dist from source update the distance of all the neighbours of u and if their prev dist was infinity then push them in q show the shortest distances from src show the distances from src to all other nodes in a graph examples graph_test graph 1 graph_test show_distances 0 distance from node 0 node 0 has distance 0 shows the shortest path from src to dest warning use it after calling dijkstra examples graph_test graph 4 graph_test add_edge 0 1 1 graph_test add_edge 1 2 2 graph_test add_edge 2 3 3 graph_test dijkstra 0 distance from node 0 node 0 has distance 0 node 1 has distance 1 node 2 has distance 3 node 3 has distance 6 graph_test show_path 0 3 doctest normalize_whitespace path to reach 3 from 0 0 1 2 3 total cost of path 6 backtracking from dest to src output 0 1 4 7 8 1 0 4 2 8 7 11 7 0 8 1 11 6 1 8 7 2 1 8 3 7 8 2 5 4 3 2 7 4 9 5 14 8 2 2 6 6 7 7 5 2 4 3 14 4 10 6 2 4 3 9 5 10 6 5 2 7 1 8 6 distance from node 0 node 0 has distance 0 node 1 has distance 4 node 2 has distance 12 node 3 has distance 19 node 4 has distance 21 node 5 has distance 11 node 6 has distance 9 node 7 has distance 8 node 8 has distance 14 path to reach 4 from 0 0 7 6 5 4 total cost of path 21
import math
import sys




class PriorityQueue:
    
    def __init__(self):
        
        self.cur_size = 0
        self.array = []
        self.pos = {}  

    def is_empty(self):
        
        return self.cur_size == 0

    def min_heapify(self, idx):
        
        lc = self.left(idx)
        rc = self.right(idx)
        if lc < self.cur_size and self.array(lc)[0] < self.array[idx][0]:
            smallest = lc
        else:
            smallest = idx
        if rc < self.cur_size and self.array(rc)[0] < self.array[smallest][0]:
            smallest = rc
        if smallest != idx:
            self.swap(idx, smallest)
            self.min_heapify(smallest)

    def insert(self, tup):
        
        self.pos[tup[1]] = self.cur_size
        self.cur_size += 1
        self.array.append((sys.maxsize, tup[1]))
        self.decrease_key((sys.maxsize, tup[1]), tup[0])

    def extract_min(self):
        
        min_node = self.array[0][1]
        self.array[0] = self.array[self.cur_size - 1]
        self.cur_size -= 1
        self.min_heapify(1)
        del self.pos[min_node]
        return min_node

    def left(self, i):
        
        return 2 * i + 1

    def right(self, i):
        
        return 2 * i + 2

    def par(self, i):
        
        return math.floor(i / 2)

    def swap(self, i, j):
        
        self.pos[self.array[i][1]] = j
        self.pos[self.array[j][1]] = i
        temp = self.array[i]
        self.array[i] = self.array[j]
        self.array[j] = temp

    def decrease_key(self, tup, new_d):
        
        idx = self.pos[tup[1]]
        
        self.array[idx] = (new_d, tup[1])
        while idx > 0 and self.array[self.par(idx)][0] > self.array[idx][0]:
            self.swap(idx, self.par(idx))
            idx = self.par(idx)


class Graph:
    def __init__(self, num):
        
        self.adjList = {}  
        self.num_nodes = num  
        
        self.dist = [0] * self.num_nodes
        self.par = [-1] * self.num_nodes  

    def add_edge(self, u, v, w):
        
        
        if u in self.adjList:
            self.adjList[u].append((v, w))
        else:
            self.adjList[u] = [(v, w)]

        
        if v in self.adjList:
            self.adjList[v].append((u, w))
        else:
            self.adjList[v] = [(u, w)]

    def show_graph(self):
        
        for u in self.adjList:
            print(u, "->", " -> ".join(str(f"{v}({w})") for v, w in self.adjList[u]))

    def dijkstra(self, src):
        
        
        self.par = [-1] * self.num_nodes
        
        self.dist[src] = 0
        q = PriorityQueue()
        q.insert((0, src))  
        for u in self.adjList:
            if u != src:
                self.dist[u] = sys.maxsize  
                self.par[u] = -1

        while not q.is_empty():
            u = q.extract_min()  
            
            
            for v, w in self.adjList[u]:
                new_dist = self.dist[u] + w
                if self.dist[v] > new_dist:
                    if self.dist[v] == sys.maxsize:
                        q.insert((new_dist, v))
                    else:
                        q.decrease_key((self.dist[v], v), new_dist)
                    self.dist[v] = new_dist
                    self.par[v] = u

        
        self.show_distances(src)

    def show_distances(self, src):
        
        print(f"Distance from node: {src}")
        for u in range(self.num_nodes):
            print(f"Node {u} has distance: {self.dist[u]}")

    def show_path(self, src, dest):
        
        path = []
        cost = 0
        temp = dest
        
        while self.par[temp] != -1:
            path.append(temp)
            if temp != src:
                for v, w in self.adjList[temp]:
                    if v == self.par[temp]:
                        cost += w
                        break
            temp = self.par[temp]
        path.append(src)
        path.reverse()

        print(f"----Path to reach {dest} from {src}----")
        for u in path:
            print(f"{u}", end=" ")
            if u != dest:
                print("-> ", end="")

        print("\nTotal cost of path: ", cost)


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    graph = Graph(9)
    graph.add_edge(0, 1, 4)
    graph.add_edge(0, 7, 8)
    graph.add_edge(1, 2, 8)
    graph.add_edge(1, 7, 11)
    graph.add_edge(2, 3, 7)
    graph.add_edge(2, 8, 2)
    graph.add_edge(2, 5, 4)
    graph.add_edge(3, 4, 9)
    graph.add_edge(3, 5, 14)
    graph.add_edge(4, 5, 10)
    graph.add_edge(5, 6, 2)
    graph.add_edge(6, 7, 1)
    graph.add_edge(6, 8, 6)
    graph.add_edge(7, 8, 7)
    graph.show_graph()
    graph.dijkstra(0)
    graph.show_path(0, 4)