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

GfG-Problem Link: bit.ly/3KeZZ7j
C++/Java/Codes and Notes Link: takeuforward.org/data-structu...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
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.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------

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

[@priyanshkumariitd]

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:)

[@priyanshkumariitd]

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

[@user-ye5zq6hr7r]

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

[@nikhilraj9900]

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

[@amanasrani6405]

understood, we are so lucky to have u striver

[@johnj171]

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

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

[@sambhavagarwal5871]

understand Thanks a lot for your immense efforts Striver.

[@dinushachathuranga7657]

excellent explanation. Lucky to find your channel.❤

[@TrendyGamer007]

loving this playlist 3000❣

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

[@cinime]

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

[@rahulprasad3575]

bro this is the exact thing i was searching today

[@hashcodez757]

Undestood BHAIYA!! thanks alot

[@vakhariyajay2224]

Thank you very much. You are a genius.

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

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

[@jambajuice07]

half way done ! wont stop

[@unfamousgaayak4838]

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

[@rishabhagarwal8049]

Understood Sir, Thank you very much

[@AYUSHKUMAR-xj4wc]

Awesome Explanation 👍👌

[@dhanashreegodase4445]

You are a Masterpeice!!

[@rishabhgupta9846]

understood,great explanation

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

[@giit85]

Great continue this series

[@harshnaruto3122]

You are hero for us

[@harleenkaur7751]

Amazing explanation. Thanks Bhaiya

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

[@A52VarshaSanga-pr7km]

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

[@namamiNarayana]

Understood! :) Thank you for your invaluable efforts striver! _/\_ ^^

[@mriduljain6809]

Understood Bhaiya😍😍

[@sagarvk18]

Love and Respect!

[@maniknr2293]

Loved it❤

[@supratimnayek2776]

Amazing explanation

[@sanketmudholkar2889]

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

[@abhinavhadole6516]

Jai Dijkstra's Algorithm 🙇🏼🙏🏻

[@amitp277]

great work 👏

[@gauravrai2979]

can someone explain the priority queue declaration part in java I don't understand the ((x,y) -> x.distance - y.distance ).

[@_hulk748]

Thankyou sir understood🙇‍♂️🙏❤

[@ananttyagi7372]

understood very well

[@banothutharun2743]

understood brother.❤

[@flip4661]

Amazing 👏

[@DevashishJose]

understood, thank you so much.

[@hrushi_borhade]

understood striver!!!

[@ruchitjoshi6889]

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

[@rahuljain224]

Superb explanation

[@Shivanai_h]

Understood 👌👌

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

[@shashankrustagi3725]

hi striver, what is shortest path faster algorithm? SPFA? is it similar to dijkstra?

[@user-kl3qv1sc8k]

amazing🤩🤩

[@gautamsaxena4647]

understood bhaiya

[@sanyam9712]

understood. Please make playlist on bit masking and bit manipulation

[@eshaanpandey7353]

Understood 👍

[@sallaklamhayyen9876]

thank you so much 🥰🥰🥰

[@sharusharath1058]

nice explaination

[@user-tk2vg5jt3l]

Thank you bhaiya

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

[@alokamgnaneswarasai5158]

Understood!

[@TarunKumar-cn6in]

Understood 🙏

[@UECAshutoshKumar]

Thank you sir 😊

[@Bhoomika_Dev]

Understood 😊

[@deepanshuchawla6493]

Is there any difference if we use queue at place of priority_queue

[@suryakiran2970]

Understood❤

[@The_Shubham_Soni]

UNDERSTOOD.

[@Sara-ed3jq]

Understoood

[@devanshgoel3433]

thank u bro!

[@p38_amankuldeep75]

understood💙💙💙

[@ranjithr6046]

can anyone say what is the need for this algorithm because we already found the shortest path in previous lectures of striver??????

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

[@DINGFULU]

pretty good video

[@SohelRana-tp8ww]

Can't thank you enough.

[@LBK3]

understood ❤

[@suhaanbhandary4009]

understood!!

[@maximelebreux2914]

Good teaching

[@user-zn3be9ik1x]

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

[@abhinandanvyas4087]

can you tell me whats the diffrence between this and video 29 is it the same?

[@priyanshvatsal9791]

Understood 😊😇

[@googleit2490]

Understood !!

[@pranavindore2410]

understood😃

[@b_01_aditidonode43]

understood sir :)

[@dreamyme543]

Understood:)

[@varunaggarwal7126]

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?

[@chiragbirla5606]

put less than or equal to

[@gouravkushwaha3001]

Is bellman ford applicable to negative weight graph?

[@shubhamkshirsagar4511]

Understood!!!

[@subhadeepghosh2813]

maza aa gya

[@soni.himansh]

Understood.

[@deepakjain4481]

well you are great simple as that

[@gunjjoshi5687]

Thank You

[@kaushalshinde3920]

understood

[@user-zr3jr7pm1c]

Nice Video

[@medhanshmathur8108]

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?

[@gametech7046]

will there be videos on union find???? Pls reply...

[@Raj-yr3vz]

is it applicable for directed graph?

[@kushagramishra3026]

"Understood'👍

[@adarshkumarrao3478]

UNDERSTOOD

[@only_for_fun1234r]

In vid 28 you solved using bfs using queue is it related to dijkstra algo.???