Dijkstra's Algorithm For Shortest Paths In Undirected Graphs
Dijkstra's single source shortest path algorithm finds shortest distances from one source to all other nodes in an undirected graph with non-negative edge weights. Time complexity: O(n+Elogn), space complexity: O(n).
In Dijkstra's single source shortest path algorithm we try to find the shortest distance from one source to all other nodes in an undirected graph. Note : We can't use the technique that we used earlier to find the shortest distance in an undirected graph where the edge weight was 1 unit. Since here the edge weight can be any number hence this approach will fail. Note: Dijkstra's fails if the graph has negative edge weight or negative edge cycle( this will put the algo in loop leading to TLE) What is Dijkstra's algorithm ? Basically we start with the source node and we traverse to all the node...