Name:________________________________________

1. (2 pts) What is the asymptotic worst-case running time of Dijkstra's single source shortest path (SSSP) algorithm on a graph G = (V,E), assuming the priority queue is implemented with a binary heap?
   
   
   
   
   
   
   
   
   
   
2. (2 pts) List one advantage of Dijkstra's SSSP algorithm over the Bellman-Ford SSSP algorithm, and one advantage of Bellman-Ford over Dijkstra.
   
   
   
   
   
   
   
   
   
3. (1 pt) True or False: Consider any undirected connected graph G = (V,E) where the weight on each edge is |V| (the number of nodes in the graph). If T is a shortest path tree in G with respect to a source node s, then T is also a minimum spannning tree of G.