The below question refers to shortest paths trees in weighted, directed graphs. Read the following carefully. Assume that No two edges have the same weight There are no cycles of net negative weight. There are no self-edges (edges leading from a vertex to itself). There are V vertices and E edges.

1. Assume that in addition to the conditions specified at the beginning, graphs are dense. If a graph contains V vertices and E edges, what is the greatest number of edges that a path in its shortest paths tree can contain?

2. Assume that in addition to the conditions specified at the beginning, there are no negative edges, graphs are dense, and they are represented with adjacency matrices. What sort of priority queue implementation would make Dijkstra's algorithm asymptotically as bad as Bellman-Ford?

a. one in which deleteMin is O(V) and insert is O(1)

b. one in which both deleteMin and insert are O(log V)

c. one in which both deleteMin and insert are O(1)

d. one in which deleteMin is O(1) and insert is O(V)