G-32. Dijkstra's Algorithm - Using Priority Queue - C++ and Java - Part 1
ฝัง
- เผยแพร่เมื่อ 6 ก.พ. 2025
- 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
@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.
i like how i can write the code myself after being 5 - 6 mins in the video.
if someone is having difficulty in getting the intuition, watch abdul sari sir once then come here for implementation.
Abdul bari*
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)
Jai Dijkstra's Algorithm 🙇🏼🙏🏻
Striver bhaiya cant thank you enough...heard the concept and coded it on one go all credits to you🙏
loving this playlist 3000❣
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.. 👍
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,
bro this is the exact thing i was searching today
This series is far better than any of the netflix original ones
understood, we are so lucky to have u striver
love you man I will watch every second!!! love you for the dedication and series you have contributed for the community
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.
IMP: when to apply -> when we have weighted undirected graph , TC -> ElogV as at max our heap has V elements
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
** 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;
}
your code is not implementing djkstra because your PQ is sorting nodes not on bases of shortest distance first, So, basically your code is just implementing BFS, distance also stored with Node in PQ so, we can process the node with shortest distance first 👍
this stuff is really code . i solved qustn on leetcode based is topic all by myself in 40 min.
Undestood BHAIYA!!
thanks alot
U r doing a great job man . Salute to you ..
You are a Masterpeice!!
You are hero for us
half way done !
wont stop
Thank you so much Striver !❤
understood Raj Bhaiya
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
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. 👍🏻
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 .
striver bhai...dadhi thodi gahri(deep) katt gayi hai side se...😅...this video is greattt.
Thank you very much. You are a genius.
excellent explanation. Lucky to find your channel.❤
Understood Bhaiya😍😍
Thank you so much ..your videos give me hope that I can do better !!
understand Thanks a lot for your immense efforts Striver.
Why the priority queue has been initialized with pair? we can simply take 2-d vector in the pq
11:51 10,5 will also be in min-heap of d,n
Superb explanation
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
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
Thank you sir 😊
understood, thanks for the great video
Understood! Super fantastic explanation as always, thank you very much!!
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
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
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
Great continue this series
Thankyou sir understood🙇♂️🙏❤
Understood Sir, Thank you very much
Love and Respect!
You are legend !
This is gold
what is the need of taking priority queue as in pair , i think there is no need of pair , we can simply take int
understood brother.❤
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.
This code is correct Dijkstra and btw Dijkstra’s algorithm does not require a visited array because the priority queue (min-heap) ensures that each node is processed in order of increasing shortest distance, so we never visit the same node again we can just update the distance of visited node and only then inserting it in PQ. And that's how real Dijkstra Works
@@tejasparse9053 Dijkstra's Algorithm Does Not Work with Negative Weights. Even if it visits nodes multiple times, Dijkstra still cannot correctly handle negative weights (even without cycles).
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?
great work 👏
Good teaching
Amazing explanation
New beard looking good
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
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?
understood,great explanation
understood striver!!!
Striver bhaiya OP
I am so so happy finally i understood this algorithm thankyou ☺
Loved it❤
amazing🤩🤩
Thank you so much!!
thank you so much 🥰🥰🥰
Thankyou very much .
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.
Thanks the tutorial is awesome.
Line number 18 should be pq.push({s,0}) ??
understood. Please make playlist on bit masking and bit manipulation
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
nice explaination
"Understood'👍
understood, thank you so much.
Understood 👌👌
UNDERSTOOD.
Understood❤
Can't thank you enough.
I think some explanations should be required in this video, First is in normal algorithm we had to keep marked nodes,
understood very well
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?
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.
Understood 👍
In vid 28 you solved using bfs using queue is it related to dijkstra algo.???
Amazing 👏
Understood 😊😇
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
done and dusted striver
telugu people attendance (from vizag)