here we can do to reduce time complexity we can use visited array and once the node is visited we wont visit it again, since all edges are of same length. We use BFS to find the minimum one only. So nearest one will always come first.
but to do that we have to increase our space complexity but i don't think introducing a visited array would make a much effect on time complexity but space complexity drastically increase.
Can we say that if we use BFS on an unweighted graph, every distance node will be updated just for once (from infinity to x), And this is the shortest distance for that node. ?
thanks striver for this amazing series... just a suggestion..if you could please add some problem links related to the particular lecture in the description so that we can practice..
i think we do not need to compare the distance of a node every time we encounter it. the first time we encounter it and change it from INF, is the shortest distance because BFS traversers level wise. so the first time it reaches a node is the shortest distance. so after we change the dist of a node from INF to some value we do not need to check that node anymore btw, thanks Striver bro. these videos help me a lot
Can we use Pair class instead of dist[]. The Pair class can have 2 properties as: int vertex and int dist_from_source. Then simply have Queue instead of Queue.
I had a question, can we do this problem like Dijikstra? Use a Priority queue where each element would be a vector containing the weight and node, sorted according to the weight? The relaxation operation is performed as it is.
Thanks for the video , would like to know 1 thing , why can't we have a visited array for nodes which have already been visited if we are using BFS because if a node is already visited and we are using BFS then that means the shortest path for that node has been already found out , so we can avoid some repetitions and not check the already visited node again
It is because if we mark the node as visited and after visiting the node one time we will not come to that node again, So after finding the distance to that node from the 1 path we can't say that the distance would be minimum, we have to check from all the paths that's why we didn't maintain the visited array.
@@rahulrawat4265 we don't need a visited array for precisely that reason. since visited nodes will not be enqueued untill they have smaller distance from src. This is not possible since BFS gives the min possible distance the first time it visits a node.
Just one question here.. I believe we can apply BFS even when the graph is weighted. Instead of adding 1 in the if statement we can add the weight of the path which will be already stored in adjacency matrix.. I am correct or is there some gap in my thinking?
Can we DFS with a visited array and another array to keep track of the min distance, while returning from DFS we will mark the vis array false for that node, in that way we can visit all possible paths and hence calculate the shortest distance. Pls, correct me if I am wrong. And which approach to follow as a general rule of thumb for these find shortest path kinds of problems and why?
@@prashantbisht2219 Yeh something like that, bt for detecting a cycle we will have to keep another array to keep track of the nodes visited in that dfs call
I'm having a doubt. Since all edges are weighted one, and we are traversing level by level, won't we get the shortest distance the first time you reach a node? Because a node will be reached first through the path having less number of nodes before it in BFS? So, once the distance of a node from the source gets updated from infinity to some other value, it won't be updated again, right? Please correct me if I'm wrong.
Yes, you are absolutely right. In this particular case where edges are weightless (common weights) the nodes once visited are not needed to be considered again. You can use a simple BFS to solve this. But when the edges are weighted you need to consider a node everytime you reach it for if you have found a cheaper path. This is the main difference between BFS and Dijkstra's Algorithm (used in this video).
DFs Code : void shortestDistanceDFs(int source, vector graph[], vector &distance) { for (auto &adjNode : graph[source]) { if ((distance[source] + 1) < distance[adjNode]) { distance[adjNode] = distance[source] + 1; shortestDistanceDFs(adjNode, graph, distance); } } } Make sure that the distance[source] is taken as zero, before functional call. This does so many unnecessary calls inorder to get the final shortest distance, BFs is way better than DFs. Just know that this can also be solved with the DFs.
Hey, I guess you are trying to ask why we are using queue here and not stack. So basically stacks follow LIFO principle and queue follows FIFO principle. In the diagram given in the video, when you are at 0 node, you push its adjacent elements i.e. 1 and 3 into the queue. What if we push these nodes in a stack? Ans: Then 1 is pushed into the stack then 3 is pushed into the stack. Now in the next iteration, when you'll pop top element from the stack, it will be 3; after processing 3 you will push its adjacent element 4 into the stack. And this process will continue as explained before. But have you observed something once you processed 3 now it was the time to process 1 because we know the fact that BFS (Breadth First Search) visits level-wise but since you used stack we processed 4 instead of 1. That's why we used queue and not the stack. Hope this helps :)
distance array should be of n+1 size right ?because if n = 8 we want to go from 0 to 8 that makes the size of array to be 9.Please correct me if I am wrong I have confusion
Why do we check again and again if the ith distance is already has given some Value For eg if 2nd index is not infinity and given some value then why we are checking for shortest path.if its not infinity then its already the shortest path? These algorithm u've explained will be better for dfs bcoz everytime we are checking multiple times until and unless we get minimal path
heY striver Sir Plz visit this If we use vis array [] instead of distance array[] and use pair ; initially push scr < node , distance = 0 > and mark visited we visited every node only one time and add +1 in distance ???
i think u can do this way but each time u visit a node, mark it unvisited after visiting it since if u don't mark it unvisited it cannot be visited again, and hence u will get the same answer from that question whether it is minimum or not
But one doubt, for calculating shortest path only one component will be there in graph or it may have multiple components ?? Because you don't used for loop in code that's why asking......., please solve my doubt
@@takeUforward if graph is connected undirected and unit weight of each edge .. Then can we use this algorithm for answering shortest distance between any two nodes? i.e. Source variable Like in question multiple queries are given Dist bw (u, v) abs (dist[v]-dist[u]) Is it the right way?
@@inclinedscorpio Yes precisely, for this exact reason we don't need a visited array since we only enqueue if we find a shorter distance to a node from source in the 2nd time or futher around. However BFS enforces that we find the shortest distance the first time around.
Is it possible to find the shorted distance in the graph without using the distance vector and just by using the visited array like marking the nodes as visited and by incrementing the counter every time we push something into the queue? Just a doubt. Thanks in advance
@@igaming_ Hi it can be avoided if we add a tuple into the queue (node,dist_from_src) and then as we reach each subsequent node we just increment the current distance by 1 and place it as our current neighbhors distance from source node.
