Question

The runtime complexity of dijkstra's algorithm when the implementation is based on a binary heap where edges e and vertices v is

Answer 1

Pseudocode

Pseudocode for Dijkstra's algorithm is provided below. Remember that the priority value of a vertex in the priority queue corresponds to the shortest distance we've found (so far) to that vertex from the starting vertex. Also, you can treat our priority queue as a min heap.

Add the starting vertex s to the initially empty fringe with priority value 0

Add all other vertices to the fringe with priority value of infinity

While the fringe is not empty:

Remove the vertex in the fringe with the minimum priority.

We'll call this vertex u.

Its priority is the shortest distance from s to u.

For each of u's neighbors v:

If v is not already in the priority queue, do nothing.

(We've already found the shortest distance from s to v.)

Otherwise, update v's predecessor to u, and update its priority value to the minimum of:

Its current priority value

The shortest distance from s to u + the weight of the edge (u, v)

Answer 2

It depends on your implementation of Dijkstra's Algorithm. Simple or Algorithm is given below with Time complexity of O(V^2). There are also some time-efficient Algorithms: Graph represented using adjacent list can be reduced to O(E log V) with the help of binary heap.