Dijkstra Algorithm

It works on graph data structure.

This algorithm is used to find shortest distance from single source to all nodes.

It can be applied on both directed and undirected graphs. It works on graphs with cycles, but it fails when it encounters negative weights.

This algorithm can be implemented using-

(1) Queue

(2) Priority Queue — Min heap data structure

(3) Set

Set is the most efficient method but priority queue method is mainly preferred for its easy implementation in different languages. There is a very minute change in time complexity while using set. Queue method undergoes unusual iterations and increases time complexity that’s why it is not preferred.

The heart of the algorithm lies in relaxation-

Relaxation:

if(dist[u] + weight <dist[v])

dist[v] = dist[u] + weight

u and v are nodes

weight is the edge weight between node u and v

Implementation-

Initially distance to all the nodes of the graph are taken as infinity and source node is taken as zero.

We start from source node and relax all the nodes of the graph.

Practical implementation and code part(Priority Queue)-

Refer

Time Complexity-

O(ElogV)

where E is the number of edges and v is the number of vertices