In the Dijkstra’s algorithm, the choice of the input graph representation and the priority queue implementation will affect its time complexity.
(a) [Algo 2] 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.
(b) [Algo 1] 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 Dijkstra’s algorithm using this setting and analyze its time complexity with respect to |V| and |E| both theoretically and empirically.
Compare the two implementations in (a) and (b) with printings of CPU time, and present your analysis on which implementation is better and in what circumstances.