Dijkstra’s Algorithm finds shortest paths from a src node to all the vertices of the graph. However it does not work for the graphs having negative weight edges. The benefit of Dijsktra’s algorithm is that it is more efficient and can be used for processing large graphs.

Note: The below implementation is optimal for sparse graphs.

Time Complexity: O(n + mlogm) where n: number of vertices and m: number of edges

In part-1, the time required to find the vertex with the least distance value and not already in the processed set, is of the order of O(n) contributing to O(n2) part of the complexity.

In this implementation, I am going to show how priority queue data structure can be used instead of an array to yield the same functionality but with a better time complexity.

Pseudo code for Dijsktra’s Algorithm (for Sparse graphs):

# Graph is represented using adjacency list representation
vector<vector<pair<int, int>>> adj;

Dijkstra(adj,src) 
{
	bool processed[V] = {false};
	int distance[V] = {INF};
	distance[src] = 0;
	priority_queue<pair<int,int>> pq;
	pq.push({0,src});

	while pq is not Empty:
	# Get the vertex which has the least distance value. 
	# This step takes O(1) time because of priority queue.
		u = pq.top().second ;
		pq.pop();
		if(processed[u]):
		 continue;
		 
		processed[u] = true; # include u in the processed set
		
		for every edge in adj[u]: # edge = {v,w} => u to v edge has weight w.
		  v = edge.v, w = edge.w; 
		  if(distance[v] > distance[u] + w):
		    distance[v] = distance[u] + w);
		    pq.push({-distance[v],v});
}

Note: Negative value of distance is pushed to the priority queue because we want the minimum distance vertex to be at the top but the default version of C++ priority queue keeps maximum element at the top.

References: cp-algorithms