Dijkstra's Algorithm Single Source Shortest Path Graph Algorithm

[@niteshgyanani9947]

Aapse acha teacher aaj tak nhi dekha...itna ache se kisi ne nhi smjhaya ye sab...you are really good ❤️❤️

[@sidhantakumarpattnaik2962]

You are awesome .I viewed almost all videos and its clear my concept , which not being cleared by seeing other videos . Keep posting new videos and this will help us .

[@kshitijarunabh968]

bro do these videos help in company placement.does it helped you...

[@RahulGvpta]

Obviously!! He works at Apple. Hope this answers your question.

[@sunnykeshshandilya1156]

Awesome man. You make any algorithms so easy and teaches 3hr things in 15 mins and concept given is very solid. One small thing missed in video.. explanation for time complexity O(E log V)

[@Dreamazium]

You do seem to be able to explain things much better than others. Uni is rubbish at explaining things while you have given me at least given me a chance of understanding it. It seems much simpler now you have explained it. Thank you.

[@DentrifixoRam88]

He's awesome

[@BackToBackSWE]

Loved the video. This was a fundamental concept in our Object Oriented 2 class.

[@adarshsharmanit356]

He is from my college , Working in Apple

[@harjos78]

One of the best and simplest videos for understandng dijkastra's algo.. Hats off Tushar... Great work!

[@DentrifixoRam88]

I just looked for a video from you about Dijkstra. You're the best teacher I've found in KZbin.

[@wth5715]

I`m student in korea. Your good explanation Thanks Tushar Roy~

[@tusharroy2525]

welcome

[@adarshsharmanit356]

@@tusharroy2525 Hello MNNITian SIR !!

[@edmondshek7072]

Roy's doing things for global audience, I benefit a lot from his videos as a Chinese student.

[@CabCallawayMusic]

The other videos explaining the algorithm aren't bad, but this is the best one when trying to understand the pseudo code and data structures - thanks!

[@blazingsniper1239]

you helped me in bachelors and need you again in masters god bless you

[@w9ahmed]

Dude, these lessons are really simple and easy to grasp. Thanks a lot, definitely helping me in my quiz tomorrow!! KEEP IT UP! :)

[@jonathanbain14]

absolutely fantastic explanation! Thank you so much for going through even the most obvious bits as now I have a -rough- idea of how i'm actually going to implement part of my algorithmics C assignment! cheers.

[@ayush47662]

Very nicely explained, especially the complexity part. I could not understand that from other sources. thank you!!

[@AvaisAhmad]

I really liked your videos. Can you please upload videos on some of following topics? ->asymtotic complexity -> n queen problem ->travelling salesman problem ->karp-rabin ->strassen matrix multiplication ->randomized algorithms las vegas and monte Carlo ->Amortized analysis ->LC Branch and Bound ->FIFO Branch and Bound ->Multistage Graph ->Flow Shop Scheduling ->binomial heap ->fibbonaci heap

[@AvaisAhmad]

+Tushar Roy thanks

[@reehji]

dude, your vids are like gold to self-learning coders :) Really appreciate the efforts!

[@mesodylaughter9327]

Thought I will never get an idea till I found this channel 😂

[@rafamassa]

First Dijkstra's explanation ever that allowed me to visualize the data transformations!

[@anamigator]

If you are still guessing, why the O(E log (v)) complexity, here is an explanation. You visit each edge in this graph at-least once (without which you cannot reach all the vertices). That would be O(E). However, at each edge, you are looking at the priority queue (heap) and doing an extractMin() operation which takes log(n) time in general, for n elements in the heap. Since in the worst case, you will have as many as V elements in the heap, each edge traversal means, a O(log V) time to extractMin from the priority queue(heap). So E times log(v).

[@maksimmartianov5189]

What about construction of the heap? Isn't it O(v) ?

[@amurto630]

Isnt extract min operation O(1) while insertion is O(logV)

[@Bdixit]

@@maksimmartianov5189 The highest degree term is considered in time complexity and hence E will be always >= V, therefore we can say total time complexity as O(E log (v))

[@Bdixit]

@@amurto630 Extract-Min in heap is an operation in which we extract root i.e. min element and then replace it with last level rightmost element and then heapify, so the total time to do this will be O(log V).

[@sureshdavid4404]

Thanks for the video . I am new for learning in youtube . i felt lot of difference to learn from videos . i have seen many videos recently , yours is fantastic . with code base .

[@crazywasy]

Tushar, thank you so much for your effort. It helps me to understand many things and succesfully take my exams. Thank you!

[@GabrielaSwanson]

Great video! Thank you so much for your clear explanations and demonstrations.

[@kaushalgala]

Watched many of your videos, and most of these videos are well explained - good for freshers to computer science, as well as those who want to dust up academics in preparation for new opportunities. Want to commend you on all your great efforts.

[@mythbuster533]

Your videos are so much better and informative than Siraj ravla's!! Great job!!

[@arthamsreenivas8858]

Great Video and this channel is my bible for programming questions.

[@mibo747]

Thanks God man. you saved me from quitting learning...

[@elegancebliss3618]

HEY I want to thank you, I will forever be grateful if I pass my exams thanks to you! keep it up man!

[@sagnik3012]

Well, did you pass? :P

[@elegancebliss3618]

@@sagnik3012 yeah I did xd

[@gowtham2775]

Thanks man, for keeping it simple and clear unlike others

[@jaimu30]

Awesome explanation man, you saved me for my final tomorrow :).

[@oknows2]

Excellent, clear explanation. Well-done.

[@technoblast4282]

your lectures were very helpful me....thanks Tushar for your wonderful videos

[@vishul1000]

One correction at 11:53 we apply extract min V times and decrease key E times. And not both E times.

[@100vivasvan]

You are AWESOME! Thank you so much God bless you! awesome video! Helped me a lot in understanding this i had struggled a lot with this algo.

[@jiakaiguo9495]

Great Explanation! Thank you so much Tushar!

[@kunalkathpal7167]

buddy you are soo good AND you explain very well!!

[@priyankakunwar8685]

U r not Tushar u r an ultimate solution

[@kiooobotu]

I like your videos a lot. This explanation of Dijkstra algorithm is one of the best I've ever seen. Have you ever thinking about make a video of A* algorithm or another search algorithm that uses heuristics? Keep making videos :) Thanks.

[@kiooobotu]

Really? I didn't see it. Thanks :)

[@shubhamsharma0420]

Man, i am speechless. Awesome video.

[@cashflow9156]

Thanks for doing a video on Dijkstra!

[@mohityadav8383]

The legend in explaining and teaching :)

[@khaledsaleh4238]

Thank you very much, Tushar. Really helpful tips and efficient code.

[@bhatwahid5107]

Wish I could have viewed these videos earlier I could have been much better in algorithims .Thankyou sir !

[@AdvaitPatel007]

Great videos buddy. Awesome job!

[@rrh2400]

So helpful and clear. Thank you so much.

[@SALMUZ]

Amazing explanation man .. that will really help me into my project. greetings ..

[@madhukiranattivilli2321]

Should use D-ary heap instead of Binary heap w/ Dijkstra's algo. D is tree order (i.e. max # of children of any node). D=log2(V) (D=E/V is another way, but log2(V) gives better performance). removemin and decrease are the 2 prominent OPs among which decrease is more frequent (O(E), removemin at O(V)). decrease causes swim whereas removemin causes sink. swim causes comparison b/w a node with it's parent, all the way till the root if required, whereas sink causes getting the smallest among all children and comparing that with the node, all the way till final level if required. So swim performs better with D-ary heap whereas sink performs better with binary heap. But since swims are more frequent than sinks, D-ary heap has to be used with D=log2(V) to strike a balance in the performance of sinks and swims. sink and swim run in O(log2(V)) time with binary heap. With D-ary heap they run in O(log(V)) time =~ O(log(V)) time

[@alifiyahh6387]

such a clear explanation thank you!!

[@Joyddep]

Really good explanation!

[@kaushalgupta7891]

awesome man, u r really helpful

[@bored78612]

Very nice explanation. Thank you.

[@Matrix_Decoded]

thankyou sooo much !!! an IP university student

[@svssukesh1170]

Clear explenation....verry helpful

[@saini85193]

Perfect as always..!

[@HarshaSuranjith]

Thanks, this helped me a lot !

[@kevinmarti2099]

Your videos are top!

[@amitgp2007]

u r excellent..Its helping ..

[@adarshchaudhary5362]

I hardly comment on videos. But man you are awesome. BTW are you IITian?

[@omkarpanhalkar6837]

he is an Apple Engineer

[@miguelangelpomahuayta253]

Genius you helped me find the error

[@jdragon8184]

at first i was using dfs to reach all vertex and update but that method was flawed thnx to him i used bfs and got correct ans for each test case

[@ganapatibiswas5858]

Why the playlist is not in organized manner ? But the video was awesome :)

[@MrDivad006]

Excellent explanation!

[@madatbrahma4389]

Hi Tushar, Your explanations on the algorithms are brilliant. Have a doubt on extracting minimum value from the map. Why are we extracting minimum value from the map? Picking up any random value/max value from the map will give the same final result. Since for every vertex, we are comparing already found distance and new distance. Only observation I found that using minimum one form the map reduces number of comparisons. Can you please put your thoughts on selecting the minimum one from the map instead of any other value?

[@michaelwaters1358]

+madat brahma I think we extract the minimum because the distance cannot be updated once it has been removed. What I mean is, if you look at his example on the board, D is the last element to get extracted. If it was the second (after the source which is A), then it would be extracted with the distance 9. This is then used to compare other paths with and therefore should not be updated (as any path that relies on D would then have to have their distance updated as well). Extracting the minimum guarantees that all the data in the distance map is the smallest value possible for that vertex. To explain this better, lets say there is a graph of 4 elements ABCD, connected like a square. A is the source, so it is extracted first. It is connected to B and D. Let's say that the edges for AB is 2, BC is 3, CD is 2, and AD is 8. If you extract at random, D could be removed next, making D have a distance set to 8. Then when you eventually extract C, it would be seen that D's distance could be updated to 7, which is less than 8. This isn't a problem at first. But if there were 5 elements, with a node E connected to D but no others, then this would require you to update the distance of E as well, because it is reliant on D's distance. This would introduce another loop of O(v) time every time you update a distance (since you have to check all the nodes that are reliant on that nodes distance). This increases the time complexity since it would occur inside the for loops that are already O(E lg (v)) (I think that's the time complexity, I could be remembering that wrong). By extracting the minimum, it guarantees that anything dependent on that node will not have to have its distance updated once it is extracted.

[@DurgeshKumawatdk]

excellent....good explanation

[@mayursandbhor8824]

videos are awesome . After doing the concept part can you please add complexity of each algorithm?

[@mayursandbhor8824]

Complexity for travelling salesman problem 0/1 Knapsack optimal BST N * queen problems

[@georgikoyrushki7825]

Hi Tushar, Thank you for your excellent explanation- just as always. I have only one question- how is the space complexity O(E + V) when in all three data structures we only store at most V elements where V is the number of vertices in the graph? This is the only thing I don't understand. Thank you :)

[@zejkeje]

the graph you are searching contains a list of vertices and their edges so I guess the space complexity is just the size of the input data in this case because the other structures are smaller

[@Khudsaybaat]

Hi

[@kishoresahoo9354]

Hi Tushar, I watched many of your algo videos... Many of the concepts are clear now. First of all A BIG THANKS for your videos. In programming part in many videos, you have used Map, LinkedList, Queue and so on. Can you post some videos where programming is done only using Arrays and Objects? Arrays like any array of objects rather using predefined java classes. e.g. int[], Object[], etc. As i need to appear few exams where we can not import any predefined class apart from java.util.Scanner;

[@rajmehta017]

Hey Tushar, we're not just extracting the minimum value but we're also removing it from the map + heap. However, in your video about Prim's, you haven't explained how to remove the minimum value from the data structure. Obviously, if we remove the top element (which is the minimum), the position of all the other elements change and in such a case, how do we update the map (which contains the positions)?

[@rajmehta017]

Here's what I did: after removing the element whose index is 0 in the heap (since it would be the lowest value), I am decrementing the index of every other element in the hash map by 1. So the element whose value in the hash map was previously 1, now becomes 0. 2 becomes 1 and so on, which is also what happens to the heap array naturally after we pop out the element at the 0th position. Thank you so much Tushar, my code is working fine, this is the first time I've implemented Dijkstra's algorithm, feels good :) Even though my code is working fine, someone do let me know whether what I did was the correct thing to do. It may be possible that my code breaks in some special cases.

[@VikramMeena1]

Nice Video... Please, Put captions above progress bar....

[@Ronakrktanna]

Hi, Can you make a video explaining the code from the Graph, Vertex and Edge classes that you have in the link you've provided? To be specific, I want to know the significance of the overridden functions that you've written and why they're coded that way. Thanks!

[@asifbilla4924]

Great explanation..

[@pravinmed]

Why do we need a Min heap ? Can we not store in the Queue instead and have a visited array to keep track of which nodes are visited prior. Although you can modify the distance but do not put back to the queue if it is already visited.

[@ashleycole3054]

Awesome Video

[@blessengeorge40]

Awesome sauce!

[@arfzp]

love u from iran semnan university

[@TusharMudgal]

very well explained..

[@garrettguitar6583]

@1:30 "The link to that video is also attached in this video here" No it's not. What is a heap? I don't know

[@swagatpatra2139]

google Priority Queue

[@saniltalathi]

Great work

[@sayed200626]

Thanks for your nice tutorial. You have mentioned this method inside Vertex class. Can you please describe this method @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + (int) (id ^ (id >>> 32)); return result; }

[@AP-eh6gr]

awesome, thanks a lot

[@harshitagarwal5188]

in this vedio u used heap+map to store the information about all the non-evaluated node, but ur implementation is in java, i wanted to know do we have something like that in c++ too, i though of using an array but finding minimum item in it would be O(size of array) and that is a costly affair, hope to get some help.

[@harshitagarwal5188]

i had used set and map to implement that, i thought of using priority_queue but at the time i didn't know how to make a min priority_queue in c++(since it is max priority queue by default), although i now know that , anyways thanks

[@snehakathare572]

Awesome....! thnx

[@NitinNataraj-gf3vx]

god bless your soul

[@shubhamojha3948]

really helpful

[@ULTIMATEGONANALIVE]

how can we update the distances, once the variable is sent in priority queue?

[@taoxie1991]

I think the easiest way is to remove the element and insert a new one.

[@pankajkalania5]

at 8:30 time what would be the value of D in Map+heap table if AD edge have weight

[@9990490677]

The value of D would be = Weight of edge AD(less than 7)

[@HappyLearningSchoolCollege9294]

nice

[@tempregex8520]

Hello @Tushar Roy why are we not using java.util.PriorityQueue and instead our own version using BinaryMinHeap? can someone explain?

[@harsheshshah5343]

Bro your voice tore my ear drums, but aside from that good tutorial!

[@veeral7632]

is Dijkstra's algo, a greedy method or dynamic or both?

[@MrDivad006]

You got the time complexity wrong. According to Fredman & Tarjan (1984), it should be O(E + V*log(V)) .

[@abhishekchaudhary2951]

well explained (y)

[@swatimaurya5424]

Thank you.sir.

[@vyomkjain]

How to find w when both value are same... Which one should be considered as minimum?

[@9990490677]

Thank you. :)

[@WeViral121]

WHY WHY in The world when a programmer is born he says "Hello World" :)

[@SanjeevkumarMSnj]

Where is the link for graph class?

[@animeworldz575]

can we use priority queue of java.util package in place of our min heap ??

[@wwxk123]

anyone know where the Vertex class came from in his code? I'm assuming its his own implementation

[@sudheerkumar4130]

Yes , its his own implementation. Graph ds can be implemented in lot of ways. Check his github github.com/mission-peace/interview/blob/master/src/com/interview/graph/Graph.java

[@rubenashughyan4273]

why didn't you just use set, or priorityQueue and prefer Heap and Map together

[@oshogarg5215]

You are GOD level in Algorithms...