Everyone having a question regarding the need of Priority Queue. The fact is that even without a Priority Queue, the algorithm will work absolutely fine, Priority Queue is just an optimizing technique here, as it always returns the minimum distance, hence we would have already figured the minimum distance of a node with least comparisons, greatly reducing the time complexity. Otherwise, if we were to use a normal Queue, we might find the shorter distance to a node in later checks. Hope you got the point!
But bro even after using Priority Queue the number of comparison are same Instead because of priority Queue Time complexity is increasing as it is contributing that log(n) factor to TC
first of all- PriorityQueue that you have used in Java code is different from what is explained. So Better way to use a PQ in JAVA is using lamba expression - PriorityQueue pq =new PriorityQueue((x, y) -> Integer.compare(x[1], y[1])); Here I am using an array {NodeValue, Distance} For People Looking for a Better Java code It is same as explained but easy - static void shortestPath(int source, int[] dest) { PriorityQueue pq = new PriorityQueue((x,y)-> x[1]-y[1]); for(int i=0;i
As suggested at 14:50 by Striver, here's my C++ solution using the Set Data Structure: #include #include #include #include using namespace std; vectorshortest_path(int n,vectoradj[],int src){ //src is the starting/source node vectordist(n+1,INT_MAX); setst; dist[src] = 0; st.insert({dist[src],src}); while(!st.empty()){ pair node = *st.begin(); st.erase(st.begin()); for(auto it: adj[node.second]){ if(node.first + it.second < dist[it.first]){ dist[it.first] = node.first + it.second; st.insert({dist[it.first],it.first}); } } }
return dist; } int main(){ int n,m,src; cin>>n>>m>>src; vectoradj[n+1]; while(m--){ int x,y,w; cin>>x>>y>>w; adj[x].push_back({y,w}); adj[y].push_back({x,w}); } vectorans = shortest_path(n,adj,src); for (int i = 1; i < ans.size(); i++) { cout
@Atul Raj in priority queue for one node we may get two different distance from source...e.g. (7,5) and (5,5) in the video....so in priority queue, we check for both first lesser distance one and then the other...the greater distance one for same node doesn't change anything but we check for that too once...but if we use set, only least distance one w.r.to one node remains in the set which is enough and we don't have to check for other distances of same node
at 15:55, I think the TC can be reduced to O(E) as we are going according to the edges not the nodes. To understand this, just consider a complete graph of size 4.. We'll have a total of 6 checks not 4 checks (4C2 = 6 = no.of edges)
Hey, thank you for your video Just a suggestion that if you could mark in video, where java code starts and ends and Cpp code starts and end would save some time for many viewers, as no one would be watching both am sure, Thanks again!
in the while loop, before iterating through neighbors, you should also add this line: if(distTo[prev] < dist) continue; without this, complexity is quadratic.
@@anirudh7137 class Solution { public: //Function to find the shortest distance of all the vertices //from the source vertex S. vector dijkstra(int V, vector adj[], int S) { priority_queue pq; vector distance(V, INT_MAX);
For all those who are wondering why we are taking the node with minimum distance from source is because for the node which has minimum distance from source in comparison to all other nodes, we have done with this node (we can't get minimum distance than it has ) and for all adjacent nodes of this node we are basically checking if distance via this min distance node to any i'th adjacent node is smaller than the dist[i]
Good explanation like always, thanks🙂❤️ Just a small add-on: thought it'd have been better if there had been a mention about negative weighted cycle (I see that you already mentioned it in Bellman Ford's, but I think adding it here also would help)
The algo mentioned by you is not exactly Dijkstra's. Dijkstra can afford to visit each node once only. Here we are processing nodes again also which deviates from the actual dijkstra's algo. This solution mentioned by you is also correct but it is doing some unneccesary calculations. Exact pseudocode used in Dijkstra's is: Dijkstra (G, w, r) { for each key ∈ G.V u.key = ∞ u.parent = NIL r.key = 0 Q = G.V while (Q ≠ ø) u = Extract-Min(Q) for each v ∈ G.Adj[u] if (v ∈ Q) alt = w(u,v) + u.key
I dnt know about sets in cpp But in java TreeSet should be used inorder to get min distance rather than normal set which only maintains the unique keys
@@takeUforward but distance can also be same eg (dist, node) - (2,3), (2,5) in this case comparator (defined by distance) will ignore the second one as it's already inserted in first one and even if we insert it by returning 1 for same distance still contains method fails for some cases as after insertion TreeSet rearrange its structure to become balance.
Yes, I also think it will work as we are checking all the nodes after all using queue. Striver, can you explain if it would make any difference using a normal queue? @take U forward
@@ketangupta221 no bro, try doing with this treee 1 2 10 2 3 15 1 4 1 4 5 1 3 6 10 5 6 1 In this queue, you will necessary travel some nodes, you reach the node 6 twice, which will be avoided in case of PQ, so in larger cases, this becomes more costlier..
Set will delete only similar pairs but 5,5 and 7,5 are different so will it delete or not 15:30 Anyone having knowledge about this please clear my doubt 2). Time complexity is O(N+E)logN and according to striver it can be O(N)logN but E>N so it must be O(E)logN ? Am I correct or wrong?
12:59 does using set improve time complexity? Erasing the element from set may add additional log(n) TC, but iterating over the edges with outdated pair in priority queue may increase TC i guess.
2:09 I used a simple queue for this problem on GFG and Coding Ninjas and it worked fine. Is there any test case I'm missing in which simple queue won't work
@striver djikstras works for all types of graphs be it undirected,directed,cyclic. Only case where it fails is if graph has negative weights. Kindly update the title of the video.
Hey striver... I guess you made a mistake in line 32 & 33...it.first is distance and it.second is next but you coded it in reverse manner. BTW loving this series ; )
Without using sets, this approach actually becomes a modified version of dijkstra algo, which works better on negative edge weights. Tell me if I'm wrong.
@@takeUforward ya ya in queue this is not sure u are getting shortest path or not. That's why you have to push single node multiple times in to queue.. I got it... Thankuu bro. U r such a supportive person 😍😍
whats difference if we take normal queue Instead of priority queue bcos we are any how adding all nodes in queue? If we r taking a node with less distance first then also we have to check for same node with more distance.like at 16:30
@@takeUforward Oh yeah,, Yeah bro I got it. I got confused in priority queue pair and adjacency list pair, both are different. {wt, node} and {node, wt} respectively. Thanks! You're helping a lot!
Hi, Thanks for the amazing lessons. I have one doubt regarding the time complexity. In the priority queue we can make maximum E entries not (N+E) because we are inserting only when we are checking adjacent nodes i.e. an edge. Then why you have mentioned the time complexity as O(N+E) log N It should be O(E log E) as per my understanding. I am confused here please correct me if I'm wrong in understanding the complexity calculations Thanks again 🙂
@ take U forward As far as i have understood we can use Queue also to get the shortest path but also we have to update the shortest path values in array multiple times. But if we use PriorityQueue it will minimize of updation of the minimum path value in array. Thats why we are using priorityQueue iver here. Am i correct ?
Hi.. You are talking about normal BFS right? We can simply use a queue and keep on checking if dis of node is minimum in our distance array. We are just using priority queue since we want to be greedy here. Even though it might backfire as well. Am I correct?
Bhai is it correct that u only inserted in p.queue when initial distance to src to that node is infinity which means u used this infinity condition like visited array??
Great video. just curious. shouldn't Time complexity be O(Nlogn + E) ?? I believe we heapify only N times not N + E. Kindly correct me if I am missing anything. Thanks for your time!
Why can you not apply the code you have written in tutorial-15 with some modification(like instead of 1 take weight and accordingly modification) because I have tested with dry run and working correctly. Can anyone help with this????
Comparable and Comparator allow you to basically do the same things. They just help you to cater to different use cases. Comparator is particularly helpful when you don't want to or can't modify the class and keep the comparision logic loosely coupled. It also allows you to pass different comparators based on your use cases at run time.
Is it the right intuition? We're using priority queues so that we don't have to revisit paths which include that vertex? Priority queue is basically ensuring that if we reach a node, we have the lowest distance from source to that node.
If the above intuition is correct. I still don't understand why is it alright to have two nodes with different distances in the priority queue. That is contradicting the above. Basically it means there are cases where we might have to revisit a vertex.
@@giteshkhanna2633 basically when two times it will have, that will be a very rare case, the second one will not bring in any adjacent nodes. So you can also use set in order to erase the prev occurrence, as I mentioned in the video as well..
@@takeUforward Thanks for the quick reply! Understood that set can help. Just wanted a little more clarity on this edge case. Will it always be at max two occurrences of the same node in the priority queue? Also what is exactly this edge case? When does this case arise exactly?
Like you reached a node, you enter that, and before visitng that again.. you again encounter that node with lesser distance so you again work on that, it can occur multiple times. But this instance will be low..
Hey striver , what is the point of taking priority queue here . Cant we just do this using queue only because somehow we will reach to node with shortest path using queue also .. For instance , in this example node 5 is visited via node 2 first yielding distance of 7, but it will further be visited by node 3 and we just update the distance if it is minimum. we can do this operation using simple queue also ....??????????????
while poping out an element from the priority queue we should check whether it has the node with the latest distance (by comparing it with the distance stored in the distTo vector), if not just pop and ignore it and pop out next. If this condition is not checked then time complexity will become quadratic and there will be no use in using a priority queue.
I did not understand why the bfs method didn't work? Also will Dijkstra work for directed graph? Is there any need to learn the same using adjacency matrix? Thanks a lot for the series!! Never expected I can be good at graph.
this won't work for all test cases. suppose a graph having u,v as edge and w as weight addEdge(u,v,w) - adding edge between u,v with weight w addEdge(0,1,5) ; addEdge(1,3,1) ; addEdge(0,2,2) ; addEdge(2,1,1) ; addEdge(2,3,7); if we consider 0 as source correct dist o/p would be 0 3 2 4 but with this algo it is 0 5 2 9 can anyone also check?
Hi striver, Thanks for making these videos. I have read that djkstras algorithm is a greedy algorithm. So once a node is visited, it does not visit it again. But you have not used a visited array here and because of that i see that this djkstras code is working even for negative weights. So Can we say that we can use djkstras algorithm even when we have negative weights to find the shortest path and this only fails if there is a negative cycle?
You're absolutely right. I read the same and watched a couple of videos before I saw this implementation without a visited array. I was doing a dry run and the same question popped in my mind and started looking for this in the comments..
When we have multiple instances of the same node in the priority queue, while popping out each node, can we not check if the distance stored in the priority queue is equal to the distance stored in the distance array and then process it? Because if the distance stored in the priority queue was greater than that in the distance array(like 7,5) then another instance of the node with the smaller distance must be processed earlier. So we can avoid processing (7,5) as soon as we pop it.
@@takeUforward yes,but I was wondering about adding a check while using priority queue like this. Would this be a correct improvisation? void Djikstra(vector&adjList,int source,int n) { vectordist(n,INT_MAX); dist[source]=0; priority_queuemin_heap; min_heap.push(make_pair(0,source)); while(!min_heap.empty()) { int node=min_heap.top().second; int distance=min_heap.top().first; min_heap.pop(); if(distance==dist[node]) { int neighbours=adjList[node].size(); cout
Don't worry the normal queue method also works fine. But for making the code efficient we are using priority queue. Here is the code by using normal queue as in the case of unweighted undirected graph: #include #include #include #include using namespace std; void shortestDistance(int n,vector * adj,int source){ queue q; vector distance(n+1,INT_MAX); distance[source] = 0; q.push(source); while(!q.empty()){ int ele = q.front(); q.pop(); for (int j = 0;j m; vector * adj = new vector[n+1]; for (int i = 0;i> u >> v >> wt; adj[u].push_back({v,wt}); adj[v].push_back({u,wt}); } for (int i = 1;i
bro in your code int next = it->first; int nextDist = it->second; if( distTo[next] > distTo[prev] + nextDist){ distTo[next] = distTo[prev] + nextDist; pq.push(make_pair(distTo[next], next)); } } yeh wala part main distance humne pair ke first part ko lia hian nah so int next = it.first kaise hua and distance it.second kaisa hua ig gala hain yeh ulta likha hia pls confirm
It is really confusing coding, because if you look at how his code works pq is storing in this order (dist, node) and adj list is storing in order (node, dist) that is why we're getting confused while traversal of adjacent nodes I hope it makes sense why it.first and it.second is reversed in the traversal of adj nodes
Do we need a priority queue here? I think it will work without the priority queue, because ultimately our ans would lie in the dist array, and we are updating it only when our condition is passed, i.e when we find a min distance of reaching the node. I am not able to figure out, how it will impact the time complexity if we just use a queue? or will it result in a wrong ans for some test cases which i can t imagine as of now, somebody pls help!
Hi Raj, instead of Dijkstras Algorithm, I can use the same algorithm used for undirected graph with unit weights and I would get the same result, how is Dijkstra different here, could you please let me know?
Yes you can, but the time complexity will be more because suppose you updated all neighbours of node x using the distance of x, but later you find a better path to reach node x, so now you not only have to update distance of node x, but also all the nodes connected to node x.
Dijkstra can also detect negative weight cycle, just by seeing if adjacent vertex is already done and its cost is still decreasing. Correct me if am wrong.
Striver one confusion is there why in priority queue we didn't ran a loop for every element why we directly put up while(!pq.empty()) but since in other questions we had checked for all the nodes why this is not so here i m getting confused in this.
@@takeUforward please upload all the other videos on the graphs like number of islands,snakes and ladders,alien dictionary and Tarjan's Algorithm please i am waiting for it.
@@nitiknarang2615 i will only upload tarjan’s algo and floyd warshall. Rest are questions implemented on the algos i taught. Those you can do after watching these videos. Everything cannot be uploded. :)
Hey Striver! Just had a doubt that like in the last video, you used Pair class to store vertex and weight, and here you are using Node class with a comparator, to store weights in PQ in min-heap fashion. Is there any other way to store vertex and weight in like that 'Pair class' method and customize our PQ in a different way? Because it is kinda difficult to understand this approach specially. Please help. Thanks for the video...
Can anyone please tell why instead of using priority queue, only simple is working and what is the time complexity if I am using queue - vector dijkstra(int V, vector adj[], int S) { vectordist(V, INT_MAX); queue q; dist[S] = 0; q.push(S); while(q.empty()==false) { int node = q.front(); q.pop(); for(vector neighbour :adj[node]){ int nextNode = neighbour[0]; int nextDist = neighbour[1]; if(dist[node] + nextDist < dist[nextNode]){ dist[nextNode]=dist[node]+nextDist; q.push(nextNode); } } } return dist; }
ua-cam.com/video/V6H1qAeB-l4/v-deo.html
Watch the above, instead of this one..
Everyone having a question regarding the need of Priority Queue. The fact is that even without a Priority Queue, the algorithm will work absolutely fine, Priority Queue is just an optimizing technique here, as it always returns the minimum distance, hence we would have already figured the minimum distance of a node with least comparisons, greatly reducing the time complexity. Otherwise, if we were to use a normal Queue, we might find the shorter distance to a node in later checks. Hope you got the point!
you can use, AVL tree, or Min stack, etc also
so true but sriver said we can not use queue why?
even in case of priority queue comparisons are same , it just reduces no of updations
But bro even after using Priority Queue the number of comparison are same
Instead because of priority Queue Time complexity is increasing as it is contributing that log(n) factor to TC
@@pranshumehta3228 exactly it is increasing just by log v if u use other data structures it might increase by V.
Oh my God.....all videos today itself ???
Great work by the way
first of all- PriorityQueue that you have used in Java code is different from what is explained.
So Better way to use a PQ in JAVA is using lamba expression - PriorityQueue pq =new PriorityQueue((x, y) -> Integer.compare(x[1], y[1]));
Here I am using an array {NodeValue, Distance}
For People Looking for a Better Java code It is same as explained but easy -
static void shortestPath(int source, int[] dest) {
PriorityQueue pq = new PriorityQueue((x,y)-> x[1]-y[1]);
for(int i=0;i
Hii striver,
Please make series on dp as well.I hope you see my comment.
Waiting for Tree Series. I know about trees but I also know if you explain tree it will much much easier.
As suggested at 14:50 by Striver, here's my C++ solution using the Set Data Structure:
#include
#include
#include
#include
using namespace std;
vectorshortest_path(int n,vectoradj[],int src){ //src is the starting/source node
vectordist(n+1,INT_MAX);
setst;
dist[src] = 0;
st.insert({dist[src],src});
while(!st.empty()){
pair node = *st.begin();
st.erase(st.begin());
for(auto it: adj[node.second]){
if(node.first + it.second < dist[it.first]){
dist[it.first] = node.first + it.second;
st.insert({dist[it.first],it.first});
}
}
}
return dist;
}
int main(){
int n,m,src;
cin>>n>>m>>src;
vectoradj[n+1];
while(m--){
int x,y,w;
cin>>x>>y>>w;
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
vectorans = shortest_path(n,adj,src);
for (int i = 1; i < ans.size(); i++)
{
cout
@Atul Raj in priority queue for one node we may get two different distance from source...e.g. (7,5) and (5,5) in the video....so in priority queue, we check for both first lesser distance one and then the other...the greater distance one for same node doesn't change anything but we check for that too once...but if we use set, only least distance one w.r.to one node remains in the set which is enough and we don't have to check for other distances of same node
Great !!
bro isme doubt hain meko ek can u please help
@@krishanpratap3286 sure bro. Pucho.
You work the hardest and give the best explanation. Striver, you are a blessing!
at 15:55, I think the TC can be reduced to O(E) as we are going according to the edges not the nodes.
To understand this, just consider a complete graph of size 4.. We'll have a total of 6 checks not 4 checks (4C2 = 6 = no.of edges)
I will be posting a video every Sunday on the other channel, so bell DABAAAAA dena: ua-cam.com/channels/vEKHATlVq84hm1jduTYm8g.html
Hey, thank you for your video
Just a suggestion that if you could mark in video, where java code starts and ends and Cpp code starts and end would save some time for many viewers, as no one would be watching both am sure, Thanks again!
Nice explanation.
Java 8+:
PorityQueue pq = new PriorityQueue((a,b)->a.weight-b.weight);
We can remove the comparator and make it shorter.
a.weight-b.weight may lead to overflow, safer to use inbuilt functions
in the while loop, before iterating through neighbors, you should also add this line:
if(distTo[prev] < dist) continue;
without this, complexity is quadratic.
ok
I'm getting wrong answer by adding this line even though this seems to be correct. Is someone else also facing the same problem?
@@anirudh7137 class Solution
{
public:
//Function to find the shortest distance of all the vertices
//from the source vertex S.
vector dijkstra(int V, vector adj[], int S)
{
priority_queue pq;
vector distance(V, INT_MAX);
distance[S] = 0;
pq.push({0, S});
while(not pq.empty()){
pair curr = pq.top();
pq.pop();
int u = curr.second;
for(vector edge : adj[u]){
int v = edge[0];
int w = edge[1];
if(min(distance[v], distance[u]+w) == distance[u]+w){
distance[v] = distance[u]+w;
pq.push({distance[v], v});
}
}
}
return distance;
}
};
man you made a complex graph algo so easy! More power to you.
For all those who are wondering why we are taking the node with minimum distance from source is because for the node which has minimum distance from source in comparison to all other nodes, we have done with this node (we can't get minimum distance than it has ) and for all adjacent nodes of this node we are basically checking if distance via this min distance node to any i'th adjacent node is smaller than the dist[i]
but couldn't we get the minimum distance information using the distance array?
Good explanation like always, thanks🙂❤️
Just a small add-on: thought it'd have been better if there had been a mention about negative weighted cycle (I see that you already mentioned it in Bellman Ford's, but I think adding it here also would help)
well according to this question, it is about "distance", and distance can't be negative.
thank you sir i solved 7 different case scenarios and in 8 hrs I have my end semester thanks a lot striver
i guess we can say, if you had a doubt that why we need PQ in this , rather than a simple modified BFS.... you are on right path
C++ code starts from 22:46
Time complexity will be E LOGN N, if E > N, which will be in most of the cases.
The algo mentioned by you is not exactly Dijkstra's. Dijkstra can afford to visit each node once only. Here we are processing nodes again also which deviates from the actual dijkstra's algo. This solution mentioned by you is also correct but it is doing some unneccesary calculations. Exact pseudocode used in Dijkstra's is:
Dijkstra (G, w, r) {
for each key ∈ G.V
u.key = ∞
u.parent = NIL
r.key = 0
Q = G.V
while (Q ≠ ø)
u = Extract-Min(Q)
for each v ∈ G.Adj[u]
if (v ∈ Q)
alt = w(u,v) + u.key
You are truly an excellent teacher, thanks :)
Finally got it... With explanation, intuition & code 🙏
Best explanation. understood , hope this channel reaches more people
I dnt know about sets in cpp
But in java TreeSet should be used inorder to get min distance rather than normal set which only maintains the unique keys
Here you store dist, node so it will work. Thanks
@@takeUforward but distance can also be same eg (dist, node) - (2,3), (2,5) in this case comparator (defined by distance) will ignore the second one as it's already inserted in first one and even if we insert it by returning 1 for same distance still contains method fails for some cases as after insertion TreeSet rearrange its structure to become balance.
The best explanation of Djikstra Algo in history of youtube.
ua-cam.com/video/sD0lLYlGCJE/v-deo.html watch this:
Striver why should we use priorty queue rather than queue, I implemented with queue also and got the same result
Yes, I also think it will work as we are checking all the nodes after all using queue.
Striver, can you explain if it would make any difference using a normal queue?
@take U forward
@@tanayshah275 It will end up taking a lot more time, as you will not get the shorter distance at first instance, will have to do a lot of rounds.
@@takeUforward That make sense, Thanks!
@@takeUforward I dont think so as in this case also u have to see all the edges. And same case with bfs using queue.
@@ketangupta221 no bro, try doing with this treee
1 2 10
2 3 15
1 4 1
4 5 1
3 6 10
5 6 1
In this queue, you will necessary travel some nodes, you reach the node 6 twice, which will be avoided in case of PQ, so in larger cases, this becomes more costlier..
Understood! So fantastic explanation as always, thank you very much!!
Set will delete only similar pairs but 5,5 and 7,5 are different so will it delete or not 15:30
Anyone having knowledge about this please clear my doubt
2). Time complexity is O(N+E)logN and according to striver it can be O(N)logN but E>N so it must be O(E)logN ? Am I correct or wrong?
True
Epic! Legendary Explanation! Thank you so much for the github code Link!
Your codes are self explanatory, better than g4g
Amazing lecture. if possible, could you please make one for Dijkstra's algorithm in DIRECTED graphs as well?
12:59 does using set improve time complexity? Erasing the element from set may add additional log(n) TC, but iterating over the edges with outdated pair in priority queue may increase TC i guess.
why cant we use the algorithm used in unit weight case??
2:09 I used a simple queue for this problem on GFG and Coding Ninjas and it worked fine. Is there any test case I'm missing in which simple queue won't work
@striver djikstras works for all types of graphs be it undirected,directed,cyclic. Only case where it fails is if graph has negative weights. Kindly update the title of the video.
I think this kind of implementation will work for negative edges also , am I right?
Hey striver... I guess you made a mistake in line 32 & 33...it.first is distance and it.second is next but you coded it in reverse manner.
BTW loving this series ; )
Mauj kardi Bhai 😁
why didi we not use a simple queue here and used a priority queue.. what is the differneve
Without using sets, this approach actually becomes a modified version of dijkstra algo, which works better on negative edge weights. Tell me if I'm wrong.
we can solve it without using priority queue.we can use simple queue.
that will work but with slightly increased T.C
A lot increased tc. As you will end up visiting all nodes multiple times instead of shorted paths..
@@takeUforward ya ya in queue this is not sure u are getting shortest path or not. That's why you have to push single node multiple times in to queue..
I got it... Thankuu bro. U r such a supportive person 😍😍
Hey, can you please share important questions to practice on these topics side by side.
whats difference if we take normal queue Instead of priority queue bcos we are any how adding all nodes in queue? If we r taking a node with less distance first then also we have to check for same node with more distance.like at 16:30
Read the other comments.. i have answered this.!
@@takeUforward ok
Hey Striver please check error in for loop
it.second=next;
it.first=nestDist;
You can check the github code link, it runs fine.
@@takeUforward No bro, Praveen S is right. There is that small error.
@@samkr200 no bro.. checked again. Look at the adjacency list, its correct, we storing the node, weight
@@takeUforward Oh yeah,, Yeah bro I got it. I got confused in priority queue pair and adjacency list pair, both are different. {wt, node} and {node, wt} respectively. Thanks! You're helping a lot!
@@takeUforward Thanks for reply I got it now Thanks a lot I'm your student in CP14
5 is repeating in queue so edges will be visited twice so what can be the time complexity.
I have seen many people using a visited array, is it really needed?? If yes, for what purpose?
Awesome, can u please also provide some more pathsorting algorithm
Hi, Thanks for the amazing lessons. I have one doubt regarding the time complexity.
In the priority queue we can make maximum E entries not (N+E) because we are inserting only when we are checking adjacent nodes i.e. an edge. Then why you have mentioned the time complexity as O(N+E) log N
It should be O(E log E) as per my understanding. I am confused here please correct me if I'm wrong in understanding the complexity calculations
Thanks again 🙂
bcoz it is checking for all nodes
bro cp algorithm ka article padho iska,ur doubt will be clear
@@manish_02291 Thank you bro :)
📢📢🙋♂️Doubt--> In C++, priority queue uses max heap, how do we create a min heap required here.
please maintain a visited array as well otherwise it will give tle for some cases.
Happy birthday bhaiya 🎂🎂🎂🎂🎂✌🏻✌🏻✌🏻
@
take U forward As far as i have understood we can use Queue also to get the shortest path but also we have to update the shortest path values in array multiple times. But if we use PriorityQueue it will minimize of updation of the minimum path value in array. Thats why we are using priorityQueue iver here.
Am i correct ?
True
@@takeUforward thanks bhaiya, much appreciated
Hi.. You are talking about normal BFS right? We can simply use a queue and keep on checking if dis of node is minimum in our distance array. We are just using priority queue since we want to be greedy here. Even though it might backfire as well. Am I correct?
@@vaishnavi9755 Yes , you are correct.
what's the problem with approaching it with normal bfs?
In C++ code, we used vector for adjacency list. shouldn't it be vector
vector is used here bcoz we need to store the node and weight only . vector of vector is not required
Dijkstra U beauty!!!!!!!
and striver u tooooooo!!!!!!!!
can we use Dikstra Algo for other graph ? like DAG ?
Hi striver, Is it important for Interviews?
Why cant we maintain the visited array and not traverse back again?
Will that raise a glitch?
Yes there might be some other way of reaching that node which is the smallest
Bhai is it correct that u only inserted in p.queue when initial distance to src to that node is infinity which means u used this infinity condition like visited array??
Great video. just curious. shouldn't Time complexity be O(Nlogn + E) ?? I believe we heapify only N times not N + E. Kindly correct me if I am missing anything. Thanks for your time!
Simply the best
Why can you not apply the code you have written in tutorial-15 with some modification(like instead of 1 take weight and accordingly modification) because I have tested with dry run and working correctly.
Can anyone help with this????
Why used Priority queye instead of queue?
If i use queue then also i will get the answer no matter i get smaller distance first or not
Best explanation 👍
I think we can implement comparable interface also in that case we don't need to pass an object of Comparator. Let me know if you disagree.
There are different ways of implementing, am new to java 😅 learned for writing code for yt videos only
@@takeUforward Thanks! I really appreciate your efforts.
Comparable and Comparator allow you to basically do the same things. They just help you to cater to different use cases. Comparator is particularly helpful when you don't want to or can't modify the class and keep the comparision logic loosely coupled. It also allows you to pass different comparators based on your use cases at run time.
bro you are saviour 💖
Why can't we use the bfs algorithm here that we used while calculating the minimum distance if the edge weights are of unit length?
Is it the right intuition? We're using priority queues so that we don't have to revisit paths which include that vertex? Priority queue is basically ensuring that if we reach a node, we have the lowest distance from source to that node.
If the above intuition is correct. I still don't understand why is it alright to have two nodes with different distances in the priority queue. That is contradicting the above. Basically it means there are cases where we might have to revisit a vertex.
@@giteshkhanna2633 basically when two times it will have, that will be a very rare case, the second one will not bring in any adjacent nodes.
So you can also use set in order to erase the prev occurrence, as I mentioned in the video as well..
@@takeUforward Thanks for the quick reply! Understood that set can help. Just wanted a little more clarity on this edge case. Will it always be at max two occurrences of the same node in the priority queue? Also what is exactly this edge case? When does this case arise exactly?
Like you reached a node, you enter that, and before visitng that again.. you again encounter that node with lesser distance so you again work on that, it can occur multiple times. But this instance will be low..
Hey striver , what is the point of taking priority queue here . Cant we just do this using queue only because somehow we will reach to node with shortest path using queue also ..
For instance , in this example node 5 is visited via node 2 first yielding distance of 7, but it will further be visited by node 3 and we just update the distance if it is minimum. we can do this operation using simple queue also ....??????????????
Yes we can use simple queue, priority queue minimizes the updations throughout the algorithms which gives us a practically better time complexity.
by using a simple queue also time complexity remains same almost then why to use min heap?
while poping out an element from the priority queue we should check whether it has the node with the latest distance (by comparing it with the distance stored in the distTo vector), if not just pop and ignore it and pop out next. If this condition is not checked then time complexity will become quadratic and there will be no use in using a priority queue.
I did this :
if(distTo[prev]
I did not understand why the bfs method didn't work? Also will Dijkstra work for directed graph?
Is there any need to learn the same using adjacency matrix?
Thanks a lot for the series!! Never expected I can be good at graph.
I think the BFS method works.
Check out this code:
#include
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector adj[n+1];
for(int i=0; i>u>>v>>w;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
vector distance(n+1, INT_MAX);
queue q;
q.push(1);
distance[1]=0;
while(!q.empty()){
int node = q.front();
q.pop();
for(auto it: adj[node]){
if(distance[node] + it.second < distance[it.first]){
distance[it.first] = it.second + distance[node];
q.push(it.first);
}
}
}
for(int i=1; i
@@jagannathank6531 does this work for every case?
@@jeal0uspengu1n Yeah it might, try out different possibilities and if it doesn't then go with what was explained in the video.
Error error on while first statement. prev=first element and dust=second element because you storing (a,at)
Can we use this for directed graph?
Do we really need to use priority_ queue ?..becoz on GFG ,My solution(contains queue) is accepted.
for optimization
why BFS will not work here....it will take more time, but i think it would work here.
this won't work for all test cases. suppose a graph having u,v as edge and w as weight
addEdge(u,v,w) - adding edge between u,v with weight w
addEdge(0,1,5) ;
addEdge(1,3,1) ;
addEdge(0,2,2) ;
addEdge(2,1,1) ;
addEdge(2,3,7);
if we consider 0 as source
correct dist o/p would be 0 3 2 4
but with this algo it is 0 5 2 9
can anyone also check?
may be because this algorithm is for undirected graph so when you add an edge (0,1,5) so you are also adding (1,0,5)...
Is there any way to do this without a priority queue?
Hi striver,
Thanks for making these videos. I have read that djkstras algorithm is a greedy algorithm. So once a node is visited, it does not visit it again. But you have not used a visited array here and because of that i see that this djkstras code is working even for negative weights. So Can we say that we can use djkstras algorithm even when we have negative weights to find the shortest path and this only fails if there is a negative cycle?
These kind of questions confuse me even more😶
You're absolutely right. I read the same and watched a couple of videos before I saw this implementation without a visited array. I was doing a dry run and the same question popped in my mind and started looking for this in the comments..
Yes, but only in a directed graph. Negative edges and SPPP does not make sense in an undirected graph
Why has he not taken the visited array. Dijstra algo says that if a node has been taken out of pq once, it cannot be insereted again.
When we have multiple instances of the same node in the priority queue, while popping out each node, can we not check if the distance stored in the priority queue is equal to the distance stored in the distance array and then process it? Because if the distance stored in the priority queue was greater than that in the distance array(like 7,5) then another instance of the node with the smaller distance must be processed earlier. So we can avoid processing (7,5) as soon as we pop it.
Yes u can use set for that case, just delete
@@takeUforward yes,but I was wondering about adding a check while using priority queue like this. Would this be a correct improvisation?
void Djikstra(vector&adjList,int source,int n)
{
vectordist(n,INT_MAX);
dist[source]=0;
priority_queuemin_heap;
min_heap.push(make_pair(0,source));
while(!min_heap.empty())
{
int node=min_heap.top().second;
int distance=min_heap.top().first;
min_heap.pop();
if(distance==dist[node])
{
int neighbours=adjList[node].size();
cout
Can a vertex be visited multiple number of times in Dijkstra
Don't worry the normal queue method also works fine.
But for making the code efficient we are using priority queue.
Here is the code by using normal queue as in the case of unweighted undirected graph:
#include
#include
#include
#include
using namespace std;
void shortestDistance(int n,vector * adj,int source){
queue q;
vector distance(n+1,INT_MAX);
distance[source] = 0;
q.push(source);
while(!q.empty()){
int ele = q.front();
q.pop();
for (int j = 0;j m;
vector * adj = new vector[n+1];
for (int i = 0;i> u >> v >> wt;
adj[u].push_back({v,wt});
adj[v].push_back({u,wt});
}
for (int i = 1;i
Bhaiya is this is the best way to solve a dijkstra based problem in contest or OA by reconstructing the adjList even if they have given??
bro in your code
int next = it->first;
int nextDist = it->second;
if( distTo[next] > distTo[prev] + nextDist){
distTo[next] = distTo[prev] + nextDist;
pq.push(make_pair(distTo[next], next));
}
}
yeh wala part main distance humne pair ke first part ko lia hian nah so int next = it.first kaise hua and distance it.second kaisa hua ig gala hain yeh ulta likha hia pls confirm
It is really confusing coding, because if you look at how his code works pq is storing in this order (dist, node) and adj list is storing in order (node, dist)
that is why we're getting confused while traversal of adjacent nodes
I hope it makes sense why it.first and it.second is reversed in the traversal of adj nodes
@@akshaysingh548 yes yes I noticed it uss time jab dry run karke dekha tha main thank you so much
Do we need a priority queue here? I think it will work without the priority queue, because ultimately our ans would lie in the dist array, and we are updating it only when our condition is passed, i.e when we find a min distance of reaching the node. I am not able to figure out, how it will impact the time complexity if we just use a queue? or will it result in a wrong ans for some test cases which i can t imagine as of now, somebody pls help!
Here you are not maintaing a processsed set, so will your method work for negative edges also. Please reply bro.
Hi Raj, instead of Dijkstras Algorithm, I can use the same algorithm used for undirected graph with unit weights and I would get the same result, how is Dijkstra different here, could you please let me know?
Yes you can, but the time complexity will be more because suppose you updated all neighbours of node x using the distance of x, but later you find a better path to reach node x, so now you not only have to update distance of node x, but also all the nodes connected to node x.
@@arnabpoddar6236 okay so in Dijkstras because of priority queue we save the time and avoid extra operations and thus its better.
@@_-6912 exactly
@@arnabpoddar6236 thank you Arnab
Thank you arnab
Why can't we use the previous Shortest path in undirected graph solution if our aim is the same?
Dijkstra can also detect negative weight cycle, just by seeing if adjacent vertex is already done and its cost is still decreasing.
Correct me if am wrong.
U r wrong, it might happen by some other path u got a largerr distance, and now its still visited but u get a better path ..
@@takeUforward(Hold my beer),.. but Dijkstra already make sure the first path we're taking is the shortest so?
@@skshma this is not the case with the priority queue implementation, a vertex may be visited multiple times from different paths
@@apoorvjain5030 actually it does make sure that if all weights are +ve,
I'm confused little bit , this can be solve using DFS or not ?
You are really very great bro
Striver one confusion is there why in priority queue we didn't ran a loop for every element why we directly put up while(!pq.empty()) but since in other questions we had checked for all the nodes why this is not so here i m getting confused in this.
Since src can only reach the nodes those are in its component, hence we did not try other components.
@@takeUforward Got it the components are connected in this case.
@@takeUforward please upload all the other videos on the graphs like number of islands,snakes and ladders,alien dictionary and Tarjan's Algorithm please i am waiting for it.
@@nitiknarang2615 i will only upload tarjan’s algo and floyd warshall. Rest are questions implemented on the algos i taught. Those you can do after watching these videos. Everything cannot be uploded. :)
@@takeUforward Sure thanks for that
cant we use the range based loop?
Why can't we use this in DAG(video 16)?
Hey Striver!
Just had a doubt that like in the last video, you used Pair class to store vertex and weight, and here you are using Node class with a comparator, to store weights in PQ in min-heap fashion.
Is there any other way to store vertex and weight in like that 'Pair class' method and customize our PQ in a different way? Because it is kinda difficult to understand this approach specially. Please help.
Thanks for the video...
Data structure is your choice bro, you can use pair, a class, whatever you feel like. Pair in itself is a pre-implemented class
@@takeUforward I was confused like if we can use this method without using comparator, or we have to implement it for sure?
@@rajatsemwal1865 comparator u can implement if u want to sort objects of that class based on custom field of that class
@take u forward, Hey sorry to disturb you again can you please let me know how compare function is called please!!!
sir topo sort + bfs vs dijkstra's which is better ?
Can anyone please tell why instead of using priority queue, only simple is working and what is the time complexity if I am using queue -
vector dijkstra(int V, vector adj[], int S)
{
vectordist(V, INT_MAX);
queue q;
dist[S] = 0;
q.push(S);
while(q.empty()==false)
{
int node = q.front();
q.pop();
for(vector neighbour :adj[node]){
int nextNode = neighbour[0];
int nextDist = neighbour[1];
if(dist[node] + nextDist < dist[nextNode]){
dist[nextNode]=dist[node]+nextDist;
q.push(nextNode);
}
}
}
return dist;
}
is this line mean
adj.get(0).add(new Node(1, 2));
adj.get(1).add(new Node(0, 2));
0 is connected to1 with weight 2
???
Yes