Graph -18: Dijkstra Algorithm (Min distance b/w source to destination in Weighted Graph)
Vložit
- čas přidán 5. 05. 2020
- Source Code:thecodingsimplified.com/dijks...
Solution:
- We'll solve it using Priority Queue (Min Heap)
- as it's weighted graph, so we'll create graph in Adjcency list, where list will contain all neighbours
- Each entry in list will be Edge (index, distance from index)
- We'll take Priority queue & boolean array & distance array
- We'll put starting edge in minHeap, mark true for this index & set 0 in Distance array for this source
- Now we'll poll top element from heap & mark this value as visited
- We'll update the distance
- At last distance array will be ready, so we'll return the value at given index
Time Complexity: O(Elog(E))
Space Complexity: O(E)
CHECK OUT CODING SIMPLIFIED
/ codingsimplified
★☆★ VIEW THE BLOG POST: ★☆★
thecodingsimplified.com
I started my CZcams channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.
★☆★ SUBSCRIBE TO ME ON CZcams: ★☆★
czcams.com/users/codingsimplif...
★☆★ Send us mail at: ★☆★
Email: thecodingsimplified@gmail.com
Thank you, great explanation.
Thank you so much for the video.
Thanks. Keep Watching
at line 45..shouldnt we add src,0 in the queue...else how can we get the neighbors of the src?
And also here we are changing the weights in the graph...so if we want to use the edges again for a different purpose..that means we can't use these edge weights/? right/?
Please upload more graph problems and also from dynamic programming.
Sure
Sir, in the if condition we are checking !visited[chileNode] along with && condition, but i think it's not required because we are not setting childNode as true vistited any where
Awesome explanation. I had one doubt, what to do if the exact path was asked, instead of the distance? Loving graphs thanks to you.
For this, you need to store Edges or indexes when you're updating distance. Try this, if you face any issue let me know.
@@CodingSimplified Okk I will
The source code in the description of the video is wrong.
Thanks Payal for notifying. The page was in old cache. I've cleared the cache, so it should be ok now. Please check the code now.
@@CodingSimplified Sir, I am not getting the code on the website for Dijkstra algorithm please provide code in the description directly...
why do we need to keep bool array and will not go to one node more than once??
Plz reply..
We need not to visit the node that we've already visited, else it'll keep on going back & forth. so to track it, we need bool array. Thanks.
how to implement Using adjacency Matrix
We've solved some Graph question using adjacency Matrix, please take help of that & still if you see difficulty in implementing then let us know.
plz provide code if we want to print the path ..
In video, I've explained how we can do it by little bit of change. Could you please try it. If you face any issue, let me know.
Also child.weight = distance[v] + dist is not required i guess
even i did not understand that point
Sir can you please make a video on how to merge two BST.
Sure, I'll try to create video on it. Thanks for your suggestion.
@@CodingSimplified THANK YOU SIR !!!