Post your questions here!

Extra resources:

Dijkstra’s visualization

Dijkstra’s step-by-step animation

Shortest Paths Lecture Posted

Post your questions here!

Extra resources:

Dijkstra’s visualization

Dijkstra’s step-by-step animation

You must be logged in to post a comment.

Powered by WordPress & Web Design Company

The way it’s written in the slides is a little misleading, considering the way we breakdown runtimes for all the other algorithms. In this part, that inner loop does not access every edge for every vertex. The inner loop is O(|E|) because for each vertex we look at, we look at each of its outgoing edges. As a result, over the course of the algorithm, we end up looking at every edge once. This is O(|E|+|V|) (in addition to the time due to priorityqueue implemenetation).

That makes sense. Cheers!

On slides 35 and 36, the while loop is O(|v|) and the method to find all edges is O(|E|). Since the method to find all edges is inside the while loop, shouldn’t the runtime of those 2 alone(assuming everything else is O(1)) be O(|V||E|) instead of O(|V|+|E|) as is displayed on slide 36.

For instance, an array/LinkedList implementation of the PriorityQueue would then be O(|V|(|V| + |E|)) ie O(|V|^2 + |V||E|) and for the heap implementation it would be O(|V|log|V| + |V||E|log|V|).