Problem $3$ Speeding up Dijkstra's Algorithm

$4$ points

In the class, we discussed the basic version of Dijkstra's algorithm whose asymptotic runtime is given by $O(|E||V|).$ The main goal of this problem is to speed$-$up Dijkstra's algorithm discussed in the class using minheap data structure.

$($a$)$ Design Dijkstra's shortest path algorithm using minheap data structure and write its pseudocode. Evaluate its asymptotic runtime theoretically. $(1$ point$)$

$($b$)$ Demonstrate the above Dijsktra's shortest path algorithm $($with $"1"$ as the start node$)$ on the unweighted, undirected graph shown in Figure $2.$ Clearly show how each node$-$attributes $($i$.$e$.$ distance estimate and parent$)$ as well as the minheap data structure changes in each iteration in both the algorithms. $(1$ point$)$

$($c$)$ Implement your pseudocode in Python as a Dijkstra$($self$,$ start$\_$vertex$)$ subroutine in the Graph class built using adjacency list representation $($similar to the one in HW$3),$ and validate your implementation on the same example graph shown in Figure $2$ by comparing its output against your answer in Problem $3($b$).(2$ points$)$