G-32. Dijkstra's Algorithm - Using Priority Queue - C++ and Java - Part 1

[@takeUforward]

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

[@sdexstarlord]

can you tell me what is the use of this priority_queuepq ?? and why did you used this vector ??

[@TrndxAtomic]

@@sdexstarlord in C++ the default priority queue is max heap...the syntax used above is for creating min-heap.

[@sukhjattana5887]

understood (Y) (Y) ....u forgot to pin this :p

[@namratam1522]

Why dont you use visited array?

[@priyanshkumar17]

understood

[@awesome_latest_virals6098]

15:26 instead of assigning value using loop , we can just write vector dist ( V , INT_MAX);

[@Cools74]

Both are same time complexity:)

[@priyanshkumar17]

yes, for more compactness of code, we can write :)

[@princenagar1686]

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.

[@visase2036]

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! 😀

[@ideepakpandey]

Wow, 3 videos on Dijkstra. We will not find such detailed videos even in expensive premium courses.

[@takeUforward]

It will be more than 3, around 10. Including problems 🫡 Give me a day or two. All will be out.

[@ideepakpandey]

@@takeUforward great🔥🙌. You are literally god for those students like me who cannot afford premium courses.

[@sharathkumar8338]

@@ideepakpandey even premium courses are not this worth. personal experience.

[@codingvibesofficial]

@take u forward That's our striver bhaiya

[@suheabkhan2546]

Learning Dijkshtra algo for the first time... And understand it in the one watch was like unbelievable.. #striver op

[@nikhilraj9900]

I have already solved more than 15 problems on Dijextra but i can't resist myself to watch whole video.

[@venkat.sairam]

🎯 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

[@shivyanshgarg2641]

i like how i can write the code myself after being 5 - 6 mins in the video.

[@CodeMode9313]

Habibi ye bhi kamal video banti ... bahut accha bahut accha

[@Moch117]

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)

[@1qwertyuiop1000]

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.. 👍

[@abhinavhadole6516]

Jai Dijkstra's Algorithm 🙇🏼🙏🏻

[@harikareddy-o4f]

Striver bhaiya cant thank you enough...heard the concept and coded it on one go all credits to you🙏

[@priyanshugupta4875]

if someone is having difficulty in getting the intuition, watch abdul sari sir once then come here for implementation.

[@therangeplus]

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,

[@TrendyGamer007]

loving this playlist 3000❣

[@sanketmudholkar2889]

This series is far better than any of the netflix original ones

[@amanasrani6405]

understood, we are so lucky to have u striver

[@raghavmanish24]

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

[@coder6109]

IMP: when to apply -> when we have weighted undirected graph , TC -> ElogV as at max our heap has V elements

[@rahulprasad3575]

bro this is the exact thing i was searching today

[@shaddyrogue9430]

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]

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???????

[@pulkitchausali1354]

@@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

[@Moch117]

No need for pair in the priority queue. Just add the node itself. We can retrieve the distance from the distance array

[@johnj171]

love you man I will watch every second!!! love you for the dedication and series you have contributed for the community

[@chiragsawarn9548]

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.

[@hashcodez757]

Undestood BHAIYA!! thanks alot

[@haha44261]

striver bhai...dadhi thodi gahri(deep) katt gayi hai side se...😅...this video is greattt.

[@ashutoshpatel2048]

this stuff is really code . i solved qustn on leetcode based is topic all by myself in 40 min.

[@apmotivationakashparmar722]

Thank you so much Striver !❤

[@princenagar1686]

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.

[@SonuKumar-ed2bo]

17:20 We need to put the node in queue for same distanse too. So we need to put a equality sign over there

[@psionl0]

Understood. In fact, I was able to solve leetCode 1514. Path with Maximum Probability without assistance after seeing this video.

[@TheRandomPerson49]

Thanks bro for telling, I also tried and solution accepted. 👍🏻

[@unfamousgaayak4838]

U r doing a great job man . Salute to you ..

[@jambajuice07]

half way done ! wont stop

[@SWEcodes]

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

[@dhanashreegodase4445]

You are a Masterpeice!!

[@harshnaruto3122]

You are hero for us

[@A52VarshaSanga-pr7km]

Thank you so much ..your videos give me hope that I can do better !!

[@AmanKumar-xw5bs]

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.

[@divyachauhan363]

exactly

[@tejasparse9053]

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.

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@GopiPusuluri-t4b]

it is better to insert in distance array when we pop out from queue, because queue already stored minimum distance with node in front

[@cinime]

Understood! Super fantastic explanation as always, thank you very much!!

[@sambhavagarwal5871]

understand Thanks a lot for your immense efforts Striver.

[@dinushachathuranga7657]

excellent explanation. Lucky to find your channel.❤

[@letstrycoding6389]

Can someone explain ..initialization of priority queue ...first line in the code...why use greater...??

[@takeUforward]

PQ by default works as max heap, with that initialisation it works as min heap

[@PriyaJain-yd7ni]

Dijkstra's works on negative weighs. It only has problem with negative weight cycles.

[@abhishekagarwal2522]

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

[@silver_shades4971]

Yeah same observation

[@aysheri8321]

hey can you give the exact implementation of dijkstra. will the priority queue approach with modification work?

[@helloworld9118]

This can also be done by taking normal queue right? As he did in G-28 video

[@rahuljain224]

Superb explanation

[@mriduljain6809]

Understood Bhaiya😍😍

[@Nikhil-Tomar]

I think some explanations should be required in this video, First is in normal algorithm we had to keep marked nodes,

[@SushmithaSathyanarayanan-u4l]

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

[@23cash86]

11:51 10,5 will also be in min-heap of d,n

[@ruchitjoshi6889]

Why the priority queue has been initialized with pair? we can simply take 2-d vector in the pq

[@sunamkundal4841]

This is gold

[@muskanagrawal7428]

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

[@cursed_nerd]

New beard looking good

[@afridihaque5700]

Striver bhaiya OP

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@maximelebreux2914]

Good teaching

[@user-zn3be9ik1x]

I am so so happy finally i understood this algorithm thankyou ☺

[@Xp-Sam]

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

[@mewerchewer7503]

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)

[@Learner_45]

@@mewerchewer7503 does that(the variant which fails for negative edges) use visited array or something like that?

[@karthik-varma-1579]

done and dusted striver telugu people attendance (from vizag)

[@sanyam9712]

understood. Please make playlist on bit masking and bit manipulation

[@kaichang8186]

understood, thanks for the great video

[@AMANMISHRA-vd7bj]

thanks God

[@AYUSHKUMAR-xj4wc]

Awesome Explanation 👍👌

[@deepakgoyal1643]

what is the need of taking priority queue as in pair , i think there is no need of pair , we can simply take int

[@kushagramishra3026]

"Understood'👍

[@UECAshutoshKumar]

Thank you sir 😊

[@sagarvk18]

Love and Respect!

[@gautamsaxena4647]

understood bhaiya

[@_hulk748]

Thankyou sir understood🙇‍♂️🙏❤

[@giit85]

Great continue this series

[@supratimnayek2776]

Amazing explanation

[@Learnprogramming-q7f]

Thank you bhaiya

[@rookiedrummer6838]

Thanks the tutorial is awesome. Line number 18 should be pq.push({s,0}) ??

[@deepalirathod4929]

You are legend !

[@rishabhgupta9846]

understood,great explanation

[@banothutharun2743]

understood brother.❤

[@banothutharun2743]

here is the python code for this problem using heap data structure import heapq class Solution: #Function to find the shortest distance of all the vertices #from the source vertex S. def dijkstra(self, V, adj, S): #code here min_heap=[] distance=[float('inf')]*V distance[S]=0 heapq.heappush(min_heap,(0,S)) while min_heap: dis,node=heapq.heappop(min_heap) for i in adj[node]: if dis+i[1]

[@sharusharath1058]

nice explaination

[@DINGFULU]

pretty good video

[@robertnant1264]

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?

[@ananttyagi7372]

understood very well

[@amitp277]

great work 👏

[@DevashishJose]

understood, thank you so much.

[@hrushi_borhade]

understood striver!!!

[@mrsohelcse]

Can't thank you enough.

[@deepakjain4481]

well you are great simple as that

[@The_Shubham_Soni]

UNDERSTOOD.

[@ashishbhardwaj4334]

Understood....

[@sallaklamhayyen9876]

thank you so much 🥰🥰🥰

[@NavyasriThalluri]

please do heap series🙏🙏🙏

[@adarshkumarrao3478]

UNDERSTOOD

[@subhadeepghosh2813]

maza aa gya

[@KUMARSAURABH-s5i]

amazing🤩🤩

[@maniknr2293]

Loved it❤

[@alibozkurt-i5r]

thanks

[@suryakiran2970]

Understood❤

[@suhaasmohandos5869]

@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?

[@rayyansyed2998]

"understood"