• In the Dijkstra's algorithm, the choice of the input graph representation and the priority queue implementation will affect its time complexity.

  1. Suppose the input graph G = (V, E) is stored in an adjacency matrix and we
     use an array for the priority queue. Implement the Dijkstra's algorithm using this setting and analyze its time complexity with respect to |V| and |E| both theoretically and empirically.
  2. Suppose the input graph G = (V, E) is stored in an array of adjacency lists and
     we use a minimizing heap for the priority queue. Implement the Dikstra's algorithm using this setting and analyze its time complexity with respect to |V| and |E| both theoretically and empirically.
  3. Compare the two implementations in (a) and (b). Discuss which implementation is better and in what circumstances.

   

  Please provide complete code in python(jupyter notebook) and related graphs for all the sub questions below with proper explanation for each part.

  (Please dont provide half code or half explanation)

  1. Provide code in python for part a) and b).
  2. Provide theoritical time complexity for part a) and b).
  3. Provide empirical time complexity for part a) and b) separately along with the code in python (Jupyter nootbook) and data visulization graphs for various |E| and |v| values example |v|=25,|v|=50,|v|=75,|v|=100.
  4. Compare the two implementations a) and b) and show which one is better using data visualization graphs for empirical time complexity and theoritical time complexity.