This question 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."

Assume in this question that 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.)

Choose from one below:

O(E log V)

O(E^2 log V)

O(E^2)

O((V+E) log V)

O(VE log V)

O(VE)

O(V^2)

O(V^2 log E)