Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
There is a problem in that is when whe check ( currentNodeDistance + distance_till_now < current NodeDistance then Assignment new shortest distance) in this line if we sum in INT_MAX with some positive value then it will become NEGATIVE and thus evaluates as Small instead of Big.
🎯 Key Takeaways for quick navigation: 00:02 📚 *Introduction to Dijkstra's Algorithm* - Dijkstra's Algorithm is crucial for solving shortest path problems. - It starts from a source node and finds the shortest distances to all other nodes. 02:35 📖 *Implementation Methods* - Dijkstra's Algorithm can be implemented using Priority Queue, Set, or Queue data structures. - Priority Queue and Set are more efficient, with Set being the fastest. 03:56 🚀 *Importance of Watching All Videos* - Emphasizes the importance of watching all videos to grasp the concept thoroughly. - Mentions that problem-solving will follow once the concept is clear. 04:09 📊 *Representing the Graph* - Explains how to represent a graph using an adjacency list with pairs (node, weight). - Provides an example of storing adjacency information. 06:04 🌐 *Initial Configuration* - Describes the initial setup, including the minimum heap data structure and a distance array. - Initializes the source node with a distance of 0. 06:19 ⏩ *Iteration Process* - Explains the iteration process, similar to BFS, where nodes are processed in order of minimum distance. - Highlights the importance of discovering shorter distances during the iteration. 11:17 🧐 *Handling Adjacent Nodes* - Details how to handle adjacent nodes and update their distances. - Demonstrates the process of selecting the best path to each adjacent node. 18:03 ❌ *Limitation: Negative Weight Cycles* - Discusses the limitation of Dijkstra's Algorithm when dealing with negative weight edges or cycles. - Explains why negative weights can lead to an infinite loop. 21:02 ⏰ *Time Complexity* - Mentions the time complexity of Dijkstra's Algorithm as O(E log V), where E is the number of edges and V is the number of nodes. - Teases upcoming explanations about priority queues and set data structures. Made with HARPA AI
Ahh Finally! Here it goes ... Happy to see you back after many days ,was waiting for the new video graph playlist. Thanks a lot for your immense efforts Striver. Good to see you in a new look! Virat Kohli of DSA! 😀
Thank you! I implemented it on my own and it worked without storing the distance on the priority queue. I only stored the nodes themselves. I also used a Pair class to store (dest,weight)
** We can use simple priority_queue i.e. there is no need to have pair inside PQ , we can take distance from distance array itself. After all there are various ways to implement so , we can do both: my code is here vector dijkstra(vector &adj, int src) { int n = adj.size(); vectordist(n,1e9); priority_queue pq; pq.push(src); dist[src]=0; while(!pq.empty()){ int node = pq.top(); pq.pop(); for(auto it:adj[node]){ int adjNode = it.first; int weight = it.second; if(dist[adjNode]>dist[node]+weight){ dist[adjNode]=dist[node]+weight; pq.push(adjNode); } } } return dist;
16:30 sir, in vectoradj[ ] given in ques, inner vector should store int, not pair how does it work for it[0] or it[1] in code, as it should have been vector
One suggestion in java code.. Instead of doing 2 operations I.E. peek() and remove() at line number 81,82& 83, we can do one operation pop().. Just an FYI for other java codes... Happy coding.. 👍
Actually, you can make it as optimal as using a set; just change one, like after pq. pop(), check if dis > dist[node], and then continue (which means skip it). This skip checking {10,5} and save time .
In this implementation it was extremely difficult to figure out the complexity. When we use a visited array, it become clear that a node may be queued multiple times but its neighbors will only be processed once. Because the first occurrence of duplicate node in the queue will have the lightest path and mark the node as visited. Eliminating the need for redundancies to be processed.
I guess if you will not check that the if dis != dist[node] we do not have to process this node as it is already processed. Because there can be same nodes with different distance in priority queue. The answer is still corrects, but i guess with your code it might lee to a worst of V.E
Understood. JAVA Code with Pair Class : class Pair{ int distance; int node; Pair(int distance,int node){ this.distance=distance; this.node=node; } } class Solution { //Function to find the shortest distance of all the vertices //from the source vertex S. static int[] dijkstra(int V, ArrayList adj, int S) { // Write your code here PriorityQueue pq=new PriorityQueue((x,y)->x.distance-y.distance); int dist[]=new int[V]; for(int i=0;i
@@Abhay-vk9uq We are overriding the comparator for PriorityQueue so that it will always keep Pair with the shortest distance at the top you have to know the lambda function and how to write own comparator for our use
This Dijkstra's algorithm is similar to Shortest Path in Undirected Graph with Unit Weights(previous video), only difference is that we don't keep track of the distance in the queue, rather we take it from distance array.I wonder if this makes a difference in the algorithm
For those who don't understand that why he take 1e9 instead of INT_MAX is because when you add something in INT_MAX then it become negative. So in line 29 of this c++ code , this will give you incorrect results.
There is a video number 28 we do the same algorithm I don't know why time complexity is better here because in that video 28 we did the shortest path from SRC with unit weight but weight is not matter here we are just adding the weight so what's the difference between exactly this algorithm or number 28 video alogrithm we exactly doing the same think
Please answer my question I have read at many places that, dijkstra cannot work for negative edge weights but I tested this algorithm for many negative edge directed graphs, and it is working fine Still I am not able to find any example of directed graph with negative edge weight where this will fail vector dijkstra(int V, vector adj[], int S) { vector distance(V, 1e9); distance[S] = 0; priority_queue pq; pq.push({0, S}); while(!pq.empty()){ auto p = pq.top();pq.pop(); int node = p.second; int dist = p.first; for(auto &x : adj[node]){ int newDist = dist + x[1]; if(newDist < distance[x[0]]){ pq.push({newDist, x[0]}); distance[x[0]] = newDist; } } } return distance; } , so why its written everywhere that it wont work for negative edge weight graph Either the above is not the actual dijkstra code, or they are wrong
There are many variants of Dijkstra. This variant allows for re-entrance of a node which allows for possibilities of further relaxation which is what happens in the case of negative edge weights but has TC of exponential (Goes from being a greedy approach to almost search the entire edge space multiple times), which often leads to TLE in contests or some harder problems. Besides, if a problem allows for negative edge weights, then there could be a possibility of a negative cycle in one of the test cases, where Dijkstra will simply fail. That is why, nobody uses Dijkstra if the question mentions the negative edge weights (unless the constraints of the graph are extremely small) and thus, most codes have implementation allowing for processing of node at maximum of one time (then it would be marked as processed or visited)
@takeUforward Do we need a visited array for Dijikstras algo? On what basis is it be decided if we need a visited array for any type of traversal including BFS/DFS?
Good explanation BUT Dijkstras algo is somewhat similar to this but little different, In this video you are visiting already visited vertices again which is just unncessary(as there are no negative edge cycles). Instead you can just make a visited array and don't visited vertices those are marked visited. Thats how the actual Dijkstras algorithm works.
Exactly. The algo he coded is working for negative weights (not cycles) because we are visiting multiple times. Took me an hour to realize this is not the correct dijkstra.
what is the need of taking heap ,cant we just go to neighbour node everytime using adjancency list and check for the distance condition whether it is greater or lower it would then automatically cover all the nodes?
So Dijkstra is basically doing level order traversal. But this time the level is represented by the distance to start node? Hence the use of a priority queue?
he explained by taking the elements as {dist, node}..but in the GFG question it is given as {node, dist}. That's why edgeweight = it[1] and node = it[0].
i think we do not need the weights in the pair as they can be accessed from the dist[node] directly. we can just put the node is the pq whenever we get a dist[node] < previous value of dist[node] and its so obvious that the new node that has been inserted into the priority queue is because of the change in the distance will be due to that node only
I also got the same doubt and I implemented Dijktra's algo using Queue which stores only adjacent nodes. It worked fine. No need to use priority queue also. The reason behind using priority queue is that, we want to order the nodes based on distance.. but here not storing distance and whenever you encounter a particular node we are getting distance from distance array. So I feel an algorithm using Queue works. I am not getting why we need 3 algorithms?
And I think the reason behind storing the distances is that to avoid traversing the multiple paths. If you store the distance in the priority queue always we get the shortest distance first and then we traverse in that path. Otherwise we could have gone in the longest path and after that we have to update each and every node to get the shortest path. If you get the shortest path first we can avoid at most longest paths.
Yes I did the same and it worked out. I think hes doing it just for clarity. You just need to store nodes only; you can get distance in the distance array since it will always be updated before we add the node to the queue
1 silly question, if you have observed striver has put distance first in priority_queue due to ease of sorting as the values are sorted based on first value, but I put distance second, and wrote a comparison function from there I observed that if i return bool operator()(pii a, pii b) { return a.second < b.second; } its giving me TLE, isn't the first value should be smaller that second when implementing min_heap, if i return opposite, its running fine, anyone has idea about it?
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
@Abhay Bisht in C++ the default priority queue is max heap...the syntax used above is for creating min-heap.
understood (Y) (Y)
....u forgot to pin this :p
Why dont you use visited array?
understood
understood
15:26 instead of assigning value using loop , we can just write vector dist ( V , INT_MAX);
Both are same time complexity:)
yes, for more compactness of code, we can write :)
There is a problem in that is when whe check ( currentNodeDistance + distance_till_now < current NodeDistance then Assignment new shortest distance) in this line if we sum in INT_MAX with some positive value then it will become NEGATIVE and thus evaluates as Small instead of Big.
🎯 Key Takeaways for quick navigation:
00:02 📚 *Introduction to Dijkstra's Algorithm*
- Dijkstra's Algorithm is crucial for solving shortest path problems.
- It starts from a source node and finds the shortest distances to all other nodes.
02:35 📖 *Implementation Methods*
- Dijkstra's Algorithm can be implemented using Priority Queue, Set, or Queue data structures.
- Priority Queue and Set are more efficient, with Set being the fastest.
03:56 🚀 *Importance of Watching All Videos*
- Emphasizes the importance of watching all videos to grasp the concept thoroughly.
- Mentions that problem-solving will follow once the concept is clear.
04:09 📊 *Representing the Graph*
- Explains how to represent a graph using an adjacency list with pairs (node, weight).
- Provides an example of storing adjacency information.
06:04 🌐 *Initial Configuration*
- Describes the initial setup, including the minimum heap data structure and a distance array.
- Initializes the source node with a distance of 0.
06:19 ⏩ *Iteration Process*
- Explains the iteration process, similar to BFS, where nodes are processed in order of minimum distance.
- Highlights the importance of discovering shorter distances during the iteration.
11:17 🧐 *Handling Adjacent Nodes*
- Details how to handle adjacent nodes and update their distances.
- Demonstrates the process of selecting the best path to each adjacent node.
18:03 ❌ *Limitation: Negative Weight Cycles*
- Discusses the limitation of Dijkstra's Algorithm when dealing with negative weight edges or cycles.
- Explains why negative weights can lead to an infinite loop.
21:02 ⏰ *Time Complexity*
- Mentions the time complexity of Dijkstra's Algorithm as O(E log V), where E is the number of edges and V is the number of nodes.
- Teases upcoming explanations about priority queues and set data structures.
Made with HARPA AI
Wow, 3 videos on Dijkstra. We will not find such detailed videos even in expensive premium courses.
It will be more than 3, around 10. Including problems 🫡 Give me a day or two. All will be out.
@@takeUforward great🔥🙌. You are literally god for those students like me who cannot afford premium courses.
@@ideepakpandey even premium courses are not this worth. personal experience.
@take u forward That's our striver bhaiya
Ahh Finally! Here it goes ... Happy to see you back after many days ,was waiting for the new video graph playlist. Thanks a lot for your immense efforts Striver.
Good to see you in a new look! Virat Kohli of DSA! 😀
Learning Dijkshtra algo for the first time... And understand it in the one watch was like unbelievable.. #striver op
Habibi ye bhi kamal video banti ... bahut accha bahut accha
I have already solved more than 15 problems on Dijextra but i can't resist myself to watch whole video.
Thank you!
I implemented it on my own and it worked without storing the distance on the priority queue. I only stored the nodes themselves. I also used a Pair class to store (dest,weight)
i like how i can write the code myself after being 5 - 6 mins in the video.
Jai Dijkstra's Algorithm 🙇🏼🙏🏻
if someone is having difficulty in getting the intuition, watch abdul sari sir once then come here for implementation.
Abdul bari*
** We can use simple priority_queue i.e. there is no need to have pair inside PQ , we can take distance from distance array itself.
After all there are various ways to implement so , we can do both:
my code is here
vector dijkstra(vector &adj, int src) {
int n = adj.size();
vectordist(n,1e9);
priority_queue pq;
pq.push(src);
dist[src]=0;
while(!pq.empty()){
int node = pq.top();
pq.pop();
for(auto it:adj[node]){
int adjNode = it.first;
int weight = it.second;
if(dist[adjNode]>dist[node]+weight){
dist[adjNode]=dist[node]+weight;
pq.push(adjNode);
}
}
}
return dist;
}
Striver bhaiya cant thank you enough...heard the concept and coded it on one go all credits to you🙏
16:30 sir, in vectoradj[ ] given in ques, inner vector should store int, not pair how does it work for it[0] or it[1] in code, as it should have been vector
thank you for explaining the stuff so well. Every other youtuber I have watched didnt help much but u explain the concept so well and you do the code,
This series is far better than any of the netflix original ones
loving this playlist 3000❣
love you man I will watch every second!!! love you for the dedication and series you have contributed for the community
understood, we are so lucky to have u striver
bro this is the exact thing i was searching today
One suggestion in java code.. Instead of doing 2 operations I.E. peek() and remove() at line number 81,82& 83, we can do one operation pop().. Just an FYI for other java codes... Happy coding.. 👍
Actually, you can make it as optimal as using a set; just change one, like after pq. pop(), check if dis > dist[node], and then continue (which means skip it). This skip checking {10,5} and save time .
thanku striver .....again i have started this series from where i have stoped due to some reasons ,,,,,i'm sure this time i will complete this
17:20 We need to put the node in queue for same distanse too. So we need to put a equality sign over there
In this implementation it was extremely difficult to figure out the complexity.
When we use a visited array, it become clear that a node may be queued multiple times but its neighbors will only be processed once.
Because the first occurrence of duplicate node in the queue will have the lightest path and mark the node as visited. Eliminating the need for redundancies to be processed.
Undestood BHAIYA!!
thanks alot
this stuff is really code . i solved qustn on leetcode based is topic all by myself in 40 min.
IMP: when to apply -> when we have weighted undirected graph , TC -> ElogV as at max our heap has V elements
I guess if you will not check that the if dis != dist[node] we do not have to process this node as it is already processed. Because there can be same nodes with different distance in priority queue.
The answer is still corrects, but i guess with your code it might lee to a worst of V.E
Understood! Super fantastic explanation as always, thank you very much!!
understand Thanks a lot for your immense efforts Striver.
excellent explanation. Lucky to find your channel.❤
U r doing a great job man . Salute to you ..
11:51 10,5 will also be in min-heap of d,n
Thank you so much Striver !❤
striver bhai...dadhi thodi gahri(deep) katt gayi hai side se...😅...this video is greattt.
Thank you so much ..your videos give me hope that I can do better !!
half way done !
wont stop
Understood. In fact, I was able to solve leetCode 1514. Path with Maximum Probability without assistance after seeing this video.
Thanks bro for telling, I also tried and solution accepted. 👍🏻
Thank you very much. You are a genius.
You are a Masterpeice!!
If u r coming from 28 video Shortest lath UG , u can easily get this only difference is we have used Prique insted of normal queue
Understood.
JAVA Code with Pair Class :
class Pair{
int distance;
int node;
Pair(int distance,int node){
this.distance=distance;
this.node=node;
}
}
class Solution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
static int[] dijkstra(int V, ArrayList adj, int S)
{
// Write your code here
PriorityQueue pq=new PriorityQueue((x,y)->x.distance-y.distance);
int dist[]=new int[V];
for(int i=0;i
Do you know what "(x,y)->x.distance-y.distance" in the line " PriorityQueue pq=new PriorityQueue((x,y)->x.distance-y.distance);" is doing???????
@@Abhay-vk9uq We are overriding the comparator for PriorityQueue so that it will always keep Pair with the shortest distance at the top
you have to know the lambda function and how to write own comparator for our use
No need for pair in the priority queue. Just add the node itself. We can retrieve the distance from the distance array
Understood Bhaiya😍😍
You are hero for us
Can someone explain ..initialization of priority queue ...first line in the code...why use greater...??
PQ by default works as max heap, with that initialisation it works as min heap
This Dijkstra's algorithm is similar to Shortest Path in Undirected Graph with Unit Weights(previous video), only difference is that we don't keep track of the distance in the queue, rather we take it from distance array.I wonder if this makes a difference in the algorithm
Understood Sir, Thank you very much
Why the priority queue has been initialized with pair? we can simply take 2-d vector in the pq
Awesome Explanation 👍👌
it is better to insert in distance array when we pop out from queue, because queue already stored minimum distance with node in front
I am so so happy finally i understood this algorithm thankyou ☺
For those who don't understand that why he take 1e9 instead of INT_MAX is because when you add something in INT_MAX then it become negative. So in line 29 of this c++ code , this will give you incorrect results.
Dijkstra's works on negative weighs. It only has problem with negative weight cycles.
There is a video number 28 we do the same algorithm I don't know why time complexity is better here because in that video 28 we did the shortest path from SRC with unit weight but weight is not matter here we are just adding the weight so what's the difference between exactly this algorithm or number 28 video alogrithm we exactly doing the same think
Superb explanation
Please answer my question
I have read at many places that, dijkstra cannot work for negative edge weights
but I tested this algorithm for many negative edge directed graphs, and it is working fine
Still I am not able to find any example of directed graph with negative edge weight where this will fail
vector dijkstra(int V, vector adj[], int S)
{
vector distance(V, 1e9);
distance[S] = 0;
priority_queue pq;
pq.push({0, S});
while(!pq.empty()){
auto p = pq.top();pq.pop();
int node = p.second;
int dist = p.first;
for(auto &x : adj[node]){
int newDist = dist + x[1];
if(newDist < distance[x[0]]){
pq.push({newDist, x[0]});
distance[x[0]] = newDist;
}
}
}
return distance;
}
, so why its written everywhere that it wont work for negative edge weight graph
Either the above is not the actual dijkstra code, or they are wrong
There are many variants of Dijkstra. This variant allows for re-entrance of a node which allows for possibilities of further relaxation which is what happens in the case of negative edge weights but has TC of exponential (Goes from being a greedy approach to almost search the entire edge space multiple times), which often leads to TLE in contests or some harder problems. Besides, if a problem allows for negative edge weights, then there could be a possibility of a negative cycle in one of the test cases, where Dijkstra will simply fail. That is why, nobody uses Dijkstra if the question mentions the negative edge weights (unless the constraints of the graph are extremely small) and thus, most codes have implementation allowing for processing of node at maximum of one time (then it would be marked as processed or visited)
@@mewerchewer7503 does that(the variant which fails for negative edges) use visited array or something like that?
Thankyou sir understood🙇♂️🙏❤
@takeUforward Do we need a visited array for Dijikstras algo? On what basis is it be decided if we need a visited array for any type of traversal including BFS/DFS?
understood. Please make playlist on bit masking and bit manipulation
what is the need of taking priority queue as in pair , i think there is no need of pair , we can simply take int
Great continue this series
Good explanation BUT Dijkstras algo is somewhat similar to this but little different, In this video you are visiting already visited vertices again which is just unncessary(as there are no negative edge cycles). Instead you can just make a visited array and don't visited vertices those are marked visited. Thats how the actual Dijkstras algorithm works.
exactly
Exactly. The algo he coded is working for negative weights (not cycles) because we are visiting multiple times. Took me an hour to realize this is not the correct dijkstra.
understood, thanks for the great video
by dijkstra can directed graph with negative edge be solved .? in this video undirected graph is used. please anyone answer
noo
what is the need of taking heap ,cant we just go to neighbour node everytime using adjancency list and check for the distance condition whether it is greater or lower it would then automatically cover all the nodes?
understood,great explanation
So Dijkstra is basically doing level order traversal. But this time the level is represented by the distance to start node? Hence the use of a priority queue?
I have seen some people are also using a processed array to track which nodes are processed why you are not doing so...?
the logic still is the same, let me know if you find some better complexity, thanks.
can someone explain the priority queue declaration part in java I don't understand the ((x,y) -> x.distance - y.distance ).
Amazing explanation
since we are not using visited array will this work on graph with -ve edge weights but no -ve cycle?
16:40 can anyone explain?
Shouldn't it be edgeweight=it[0] and node=it[1] ?
I'm a bit confused over here
he explained by taking the elements as {dist, node}..but in the GFG question it is given as {node, dist}. That's why edgeweight = it[1] and node = it[0].
@@autobotin does that mean it[1] points for first element and it[0] points for second element in { dist (1st) , node(2nd) } pqueue
@@dhanushdm5761 it[0] point to the first element i.e. node and it[1] points to the secong element i.e. distance.
@@autobotin ok ok according to gfg problem.. ->o for node and 1 for distance
if i store the pq as ({node , wieght}) would there be any issue , it works fine on gfg , rest understood
watch the third video of dijksta, you will know why it worked
@@takeUforward han bhaiya dekhaa 😂 🤣 u r a truee mentor... 36th se jo questions hai usme aur clear ho gaya
can anyone say what is the need for this algorithm because we already found the shortest path in previous lectures of striver??????
i think we do not need the weights in the pair as they can be accessed from the dist[node] directly. we can just put the node is the pq whenever we get a dist[node] < previous value of dist[node] and its so obvious that the new node that has been inserted into the priority queue is because of the change in the distance will be due to that node only
I also got the same doubt and I implemented Dijktra's algo using Queue which stores only adjacent nodes. It worked fine. No need to use priority queue also.
The reason behind using priority queue is that, we want to order the nodes based on distance.. but here not storing distance and whenever you encounter a particular node we are getting distance from distance array. So I feel an algorithm using Queue works. I am not getting why we need 3 algorithms?
And I think the reason behind storing the distances is that to avoid traversing the multiple paths. If you store the distance in the priority queue always we get the shortest distance first and then we traverse in that path. Otherwise we could have gone in the longest path and after that we have to update each and every node to get the shortest path. If you get the shortest path first we can avoid at most longest paths.
Yes I did the same and it worked out. I think hes doing it just for clarity. You just need to store nodes only; you can get distance in the distance array since it will always be updated before we add the node to the queue
New beard looking good
understood brother.❤
Love and Respect!
Thanks the tutorial is awesome.
Line number 18 should be pq.push({s,0}) ??
Striver bhaiya OP
great work 👏
I think some explanations should be required in this video, First is in normal algorithm we had to keep marked nodes,
Why we are using PriorityQueue of , if we can find shortest path using PriorityQueue of only ??
distance is what helps us pick the next optimal node to be explored
Understood! :)
Thank you for your invaluable efforts striver! _/\_ ^^
Is bellman ford applicable to negative weight graph?
Thank you sir 😊
In vid 28 you solved using bfs using queue is it related to dijkstra algo.???
Good teaching
Loved it❤
done and dusted striver
telugu people attendance (from vizag)
You are legend !
1 silly question, if you have observed striver has put distance first in priority_queue due to ease of sorting as the values are sorted based on first value, but I put distance second, and wrote a comparison function from there I observed that if i return bool operator()(pii a, pii b) {
return a.second < b.second;
} its giving me TLE, isn't the first value should be smaller that second when implementing min_heap, if i return opposite, its running fine, anyone has idea about it?
put less than or equal to
"Understood'👍
understood, thank you so much.
thank you so much 🥰🥰🥰
Can you please tell how much videos are left for this series?
You can check A2Z sheet, we will cover all of them in the graphs section
@@takeUforward time? Tb tk pura upload ho jaayaga
@@harshdasila6680 Trying bro asap, kyu ki office rehta hai na.
@@takeUforward yes bro i understand ❤️
understood striver!!!
hi striver, what is shortest path faster algorithm? SPFA? is it similar to dijkstra?