Dijkstra's Algorithm Part 1

Dijkstra’s Algorithm finds shortest paths from a src node to all the vertices of the graph like Bellman-Ford Algorithm. 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 dense graphs.

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

In case of sparse graphs, the complexity can be reduced to O(n + mlogm) using priority queue data structure of STL.

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

Dijkstra(Graph,src) # Graph is represented here using adjacency matrix. 
{
	bool processed[V] = {false};
	int distance[V] = {INF};
	distance[src] = 0;
	for i = 1 to i = n-1:
	
	# Get the vertex which is not already processed and 
	# has the least distance value. This step takes O(n) time.
		u = minDist(distance,processed); 
		
		if(distance[u] = INF)  # Now remaining vertices are unreachable from src,
		 break;				   # so break the loop.
		 
		processed[u] = true; # include u in the processed set
		for every neighbour v of u:
		 if(!processed[v]):
		  distance[v] = min(distance[v],distance[u] + Graph[u][v]);		  
}
			

References: GeeksforGeeks