G-32. Dijkstra's Algorithm - Using Priority Queue - C++ and Java - Part 1
HTML-код
- Опубликовано: 15 окт 2024
- GfG-Problem Link: bit.ly/3KeZZ7j
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
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
can you tell me what is the use of this priority_queuepq ??
and why did you used this vector ??
@@sdexstarlord 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
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.
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
i like how i can write the code myself after being 5 - 6 mins in the 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 have already solved more than 15 problems on Dijextra but i can't resist myself to watch whole video.
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.. 👍
Habibi ye bhi kamal video banti ... bahut accha bahut accha
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,
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.
Striver bhaiya cant thank you enough...heard the concept and coded it on one go all credits to you🙏
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.
Why the priority queue has been initialized with pair? we can simply take 2-d vector in the pq
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 series is far better than any of the netflix original ones
IMP: when to apply -> when we have weighted undirected graph , TC -> ElogV as at max our heap has V elements
loving this playlist 3000❣
Jai Dijkstra's Algorithm 🙇🏼🙏🏻
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?
what is the need of taking priority queue as in pair , i think there is no need of pair , we can simply take int
striver bhai...dadhi thodi gahri(deep) katt gayi hai side se...😅...this video is greattt.
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
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
understood, we are so lucky to have u striver
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
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
Thanks the tutorial is awesome.
Line number 18 should be pq.push({s,0}) ??
love you man I will watch every second!!! love you for the dedication and series you have contributed for the community
17:20 We need to put the node in queue for same distanse too. So we need to put a equality sign over there
bro this is the exact thing i was searching today
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?
🎯 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
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. 👍🏻
this stuff is really code . i solved qustn on leetcode based is topic all by myself in 40 min.
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 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.
@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?
Could you please provide sample inputs for every problem its really painstaking to create a request
since we are not using visited array will this work on graph with -ve edge weights but no -ve cycle?
can anyone say what is the need for this algorithm because we already found the shortest path in previous lectures of striver??????
I think some explanations should be required in this video, First is in normal algorithm we had to keep marked nodes,
Undestood BHAIYA!!
thanks alot
U r doing a great job man . Salute to you ..
understood. Please make playlist on bit masking and bit manipulation
Thank you so much ..your videos give me hope that I can do better !!
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
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?
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
Won't this algorithm work for -ve weight edges and only fail in case of cycles.
half way done !
wont stop
Dijkstra's works on negative weighs. It only has problem with negative weight cycles.
can someone explain the priority queue declaration part in java I don't understand the ((x,y) -> x.distance - y.distance ).
Understood ❤
In vid 28 you solved using bfs using queue is it related to dijkstra algo.???
by dijkstra can directed graph with negative edge be solved .? in this video undirected graph is used. please anyone answer
noo
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
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
You are a Masterpeice!!
Thank you very much. You are a genius.
excellent explanation. Lucky to find your channel.❤
11:51 10,5 will also be in min-heap of d,n
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.
understand Thanks a lot for your immense efforts Striver.
are questions from this graph series after its completed enough
understood, thanks for the great video
Is bellman ford applicable to negative weight graph?
can you tell me whats the diffrence between this and video 29 is it the same?
You are hero for us
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
Understood! Super fantastic explanation as always, thank you very much!!
Superb explanation
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 ❤️
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
I am lost. Why you are conisdering node value to poll from PQ instead of distance?
May you please elaborate more on your question? I didn't quite understand it.
That is not exactly Dijkshtra's algorithm. Here you are reprocessing the nodes by putting them into queue again. The algorithm you gave will actually work for negative edges. It can't handle negative loop weights. Also, this is against the ideas of greedy algorithm, that once you find the minimum/maximum for a path, you don't revisit it. This algorithm you've given can be seen as an improved version of Belmann Ford with the complexity bigger than ELOGV
Yeah same observation
hey can you give the exact implementation of dijkstra. will the priority queue approach with modification work?
This can also be done by taking normal queue right?
As he did in G-28 video
hi striver, what is shortest path faster algorithm? SPFA? is it similar to dijkstra?
is it applicable for directed graph?
will there be videos on union find???? Pls reply...
Understood Sir, Thank you very much
Why dont we consider visited node here?
Amazing explanation. Thanks Bhaiya
Understood Bhaiya😍😍
why don't we just use a queue, I mean what's the benefit of using a priority queue anyway?
Is there any difference if we use queue at place of priority_queue
Thankyou sir understood🙇♂️🙏❤
Awesome Explanation 👍👌
Will Dijkstra's Algo work with negative weights in a DIRECTED graph?
Next video we have discussed
please do heap series🙏🙏🙏
I am so so happy finally i understood this algorithm thankyou ☺
You are legend !
Thank you sir 😊
Good teaching
I am guessing Video 28 was Dijkstra with Queue?
Why did we use min-heap instead of a simple Queue?
We want the node with least distance
understood brother.❤
understood,great explanation
Great continue this series
Love and Respect!