Description
CE2101/CZ2101
ALGORITHM DESIGN AND ANALYSIS
Project 2: Dijkstra’s Algorithm
In the Dijkstra’s algorithm, the choice of the input graph representation and the priority queue implementation will affect its time complexity.
(a) 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) 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.
Reviews
There are no reviews yet.