Dijkstra algorithm | Code implementation
Вставка
- Опубліковано 25 сер 2024
- This video explains the implementation with code for the dijkstra algorithm which is also known as the single source shortest path algorithm.In this video, I have first shown the steps for the algorithm and then i have analyzed what data structures are required to find the shortest path from the source node to every other node or vertex.I have taken the simple implementation for easier understanding using arrays.You can implement using SET or MAP as well.I have shown dry run for an example and at the end of the video, i have shown the code walk through and explanation.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL VIDEOS:-
Dijkstra algorithm: • Dijkstra algorithm | S...
Awesome explanation.. it would be better if u could show the implementation using priority queue and adj list
this is the only video on youtube of Dijkstra algorithm which explains as well as implement the algorithm.
Very well explained . Helpful for the many tier 3 college students.
I like how you always say "I hope you are understanding this." I am understanding this :)
Nice 😀
Additional note to the video:
SSSP in a directed acyclic graph can be found in O(V+E) by finding topological sort ordering of the graph.
Excellent ! how neat and superb explaination it was with proper examples and dry run.
Thanks 😊
Exactly what i was looking for. Thank you sir.
Welcome :)
Thank you so much for the video. It helps me to understand this algorithm better!
Nice :)
God Bless you, man! So there is only 1 line of difference in code between PRIMS and Dijkstra!
Yes
I think it is best explanation on youtube on this topic, it is awsm
Helpful 🙂
Thanks for creating this series of videos. Can you please add LLD and HLD playlist or point to some good resources for them.
Simple and clear!
:)
just went to your website, feels good to know that you are a fellow shinobi
😂❤️
@@techdose4u That's you Ninja way.
Thanks...
Simple and clear explanation.
Welcome :)
i appreciate your work..a very very thank you sir.
Welcome bro :)
Thanks so much for the video. Among other videos on youtube on Dijkstra's algorithm this was the best.
Can you please answer if the algorithm works (without any modification) even if more than one unprocessed nodes are minimum cost at any iteration?
Yes it does. You can choose any one.
Wow 😊 beautiful video everything very clear in this video.. thanking you so much sir ❤️😍😇
Welcome bro :)
Good explanation, But I want to see how we can use heap(priority_queue) for optimization version because during updation of distance we can't update it directy in heap(priority_queue) . There is no decrease key operation available in priority queue.
For this we have to define our own min_heap with some some changes. So if you have solution then please ans it so we can use priority_queue.
Hmmm...I will show it in some problem
As always! Spot on great explanation.
Thanks :)
@@techdose4u One Q.. Are you planning to cover Bellman-Ford too? for -ve weight cycles..
@@techdose4u can you explain dijkstra by adjacency list and min heap
Thank you sirrrrr superrr explaination
Thanks
THANK YOU !!!!!!!!!!!
Welcome
understood :) thank you bhaiya
Welcome :)
Very nice explanation 🙂
Thanks
Thank you Sir 💖
Welcome :)
thank you sir!
just awesome...
Thanks
Very nice explanation! Thanks! one small doubt, using the adjacency list how will it improve the time complexity?
If the graph is sparse use list otherwise array.
Please also include code for Priority Queue implementation. Why create half videos.
Anyways the explanation is excellent.
It's easy to replace the priority queue code :)
Sir regarding every algo implementation....it should be practised on daily basis ?
You should practice atleast 1 problem daily from the topic you feel uncomfortable with.
I have seen another way of doing it using heap which i think is more time efficient but more complicated, which one should i try because i find the heap one a little difficult to understand?
Heap is also easy. I have explained the simplest approach which everyone can understand but you can use priority queue STL/library to implement heap :)
Excellent explanation! Could you please make a video on 0-1 BFS as well?
Sure. But it will take time since I want to complete the course 😅
@@techdose4u Surely, Sir! Please take your time. 😄
Thanks is a precious explanation. Can I ask you if Dijkstra's algorithm is the one used in the Amazon warehouses to define the pick paths for the pickers?
yes
@@adithyav9283 thanks can you suggest me some readings about it?
can we just take a queue and only push to it if the value of vertex is updated, we can skip the visited array and looping through all vertices thing right?
What kind of traversal is better for this algorithm ? Dfs or bfs
Hey Buddy, very nice explanation. Can I know what do you use to write and record?
Sir please make a video on Josephus Problem
Sure bro. I will make it but after finishing current series.
13:20 Is this process necessary? To go and check which nodes haven't been visited...?
Why to use Dijkstra's algorithm when the BFS using a queue can be used to find minimum distance of nodes from a given source in O(V + E) time complexity.
Can you share the code for this?
Isn't is same as Prim's algo ?
will this code give wrong answers for negative weight edges
Can you execute the code in code blocks and show it?
Here the adjacency matrix is created and this doesn't change with the variables. looks like this is hardcoded
And if you have to create this matrix dynamically you should be going through the given data i guess
Adjacency matrix is hardcoded but you can always create taking inputs.
can anyone post the link for dijkstra's algo implemented using minheap in java?
sir can you please show the java code too
I am providing java codes now. But I did not provide back when I made these videos. I will add them.
7:46
Sir, why are you always taking minimum distance vertex from VALUE Array , what is the logic behind that ??
Because we want to make a greedy decision to select minimum cost path from all adjacent edges.
How to get distance between neighbours and get neighboursnames
sir plzz ap yeh dijkstras algorithm ke notes aur coding bhej dijey takhe mein apne paas download kar sakhun plzz?
Relax?
content is good but voice is tooo low