Shortest Paths These questions concerns 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

When I say

• "the lightest edge" I mean "the edge with the smallest weight."
• "the heaviest edge" I mean "the edge with the largest weight."

Question 2 2 pts Assume in this question that, in addition to the conditions specified at the beginning of the quiz, there are no negative edges, graphs have at least as many edges as vertices, and graphs are represented with a list containing all of the graph's edges. Within the list, each edge is represented with an ordered pair. Assuming that the graph representation is at no point converted to a more efficient form, what is the tightest upper bound that can be put on Dijkstra's algorithm. (Assume that Dijkstra's algorithm uses a binary heap.) O(V^2) O(V 2 log E) O(E^2log V) O(VE) O(CV+E) log) O(VE log ) O(E^2) O(E log V) Question 3 2 pts Assume in this question that, in addition to the conditions specified at the beginning of the quiz, 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? (Give an exact answer, simplified as much as possible, with no white space.) Question 2 2 pts Assume in this question that, in addition to the conditions specified at the beginning of the quiz, there are no negative edges, graphs have at least as many edges as vertices, and graphs are represented with a list containing all of the graph's edges. Within the list, each edge is represented with an ordered pair. Assuming that the graph representation is at no point converted to a more efficient form, what is the tightest upper bound that can be put on Dijkstra's algorithm. (Assume that Dijkstra's algorithm uses a binary heap.) O(V^2) O(V 2 log E) O(E^2log V) O(VE) O(CV+E) log) O(VE log ) O(E^2) O(E log V) Question 3 2 pts Assume in this question that, in addition to the conditions specified at the beginning of the quiz, 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? (Give an exact answer, simplified as much as possible, with no white space.)