Easier to understand when paired with Mike Pound's explanation of how Dijkstra's Algorithm finds the shortest path. Eleven-minute explanation on Computerphile: ua-cam.com/video/GazC3A4OQTE/v-deo.html
All the people criticizing this man's teaching have some serious issues. I had no issues in absorbing the information he taught in this lecture. If you all are annoyed, 'distracted' because of how he can pause or talk slowly sometimes, then you yourself are the problem imo. Concentrate on the information being taught not hyper fixate on nothing.
great lecture, thanks mit! I have a doubt, in the dag relaxation algo we init the distance estimate from the source to the source equal to 0, but the professor said that this value could negative or -infinity, however that can occur when the graph has a negative cycle, given that the graph is a DAG then the shortest path distance from the source to the source has to be 0 because DAG has no cycles
d(s,u) isn't infinity, because you're starting from d(s,s), which is 0. Then you get to the next node, say t. d(s,t) = infinite > d(s, s) + w(s, t), so d(s, t) = d(s, s) + w(s, t). So you need a starting point, and that starting point is the distance estimate from your source node to your source node. I think the reason you can't just say delta(s, u) is because you're not certain yet that it's actually the shortest path. Only at the end, when the algorithm 'converges', and the triangle inequality holds for all vertices, can you actually say that your d's (your estimates) are the deltas (shortest paths)
@@robje185 but I think d(s,v)>delta(s,u)+w(u,v) can be correct if vertex u comes before v in topological order.because d(s,u) is the same as delta(s,u) as there is no subroute that can reach vertex u from vertex s going through any vertex that come after u in the topological order. am I right?
2 роки тому+1
Instructor Solomon is watching there on the audience? (right-side of the video)
hey, i think i caught a slight mistake in the description. it says the instructor is erik demaine but isnt it jason ku? either way, thank you so much for giving us free access to such great courses and lectures. im still in high school but watching these makes me even more excited to major in cs at uni. i dont completely understand everything but the instructors are so good ive binge watched them all in like two days. im definitely coming back to this course when i start this topic at uni. ive got a feeling its going to be extremely helpful.
This guy does not prepare for the lectures at all. He fumbles every 1.4 seconds and takes forever to construct a sentence and gets confused himself, mid-sentence. FOR ALL THOSE WATCHING: for this and the next three lectures on shortest paths, please go through the notes first and/or watch the 2011 version. Jason Ku really needs to improve his teaching skills.
@@Karim-nq1be The problem is 1) it's distracting af (and that's the main one), and 2) he says it so randomly that not only is nobody going to be nodding (especially in an auditorium where seeking feedback is meaningless), but it's obvious that he's more doing it as a coping mechanism to convince himself that he's actually teaching well when he isn't, so it's also annoying af
@@WeirdAlSuperFan interesting take that feedback is meaningless when you realize that the other instructors attend every lecture and correct mistakes when they occur
0:00
3:26
10:33
17:40
21:10
27:38
35:45
44:28
50:28
54:36
These videos are awesome prep for sde interviews
Easier to understand when paired with Mike Pound's explanation of how Dijkstra's Algorithm finds the shortest path. Eleven-minute explanation on Computerphile: ua-cam.com/video/GazC3A4OQTE/v-deo.html
Just be aware that Dijkstra's is non-negative and not involving DAG -- Jason explains it at 50:39 similarly.
Great videos, I love this series.
I'm facing hard time understand the graphs first was with the BFS and DFS thank god i just understaned them now with shortestpath algorithm any tips
All the people criticizing this man's teaching have some serious issues. I had no issues in absorbing the information he taught in this lecture. If you all are annoyed, 'distracted' because of how he can pause or talk slowly sometimes, then you yourself are the problem imo. Concentrate on the information being taught not hyper fixate on nothing.
great lecture, thanks mit! I have a doubt, in the dag relaxation algo we init the distance estimate from the source to the source equal to 0, but the professor said that this value could negative or -infinity, however that can occur when the graph has a negative cycle, given that the graph is a DAG then the shortest path distance from the source to the source has to be 0 because DAG has no cycles
Just wondering where all the students go. I saw them in previous lectures...
covid pandemic started; we left campus
I also wondering same 😂
they are missing after Solomon shouted on them in one of the graph lectures
52:00 The professor walks for 7 seconds to get to the right most black board... When I was in uni, there were only 2 in a classroom. The difference..
42:30 shouldnt it be d(s, v) > delta(s, u) + w(u,v)? bcoz d(s,u) is also an upper bound estimate, i.e, infinity
d(s,u) isn't infinity, because you're starting from d(s,s), which is 0. Then you get to the next node, say t. d(s,t) = infinite > d(s, s) + w(s, t), so d(s, t) = d(s, s) + w(s, t). So you need a starting point, and that starting point is the distance estimate from your source node to your source node.
I think the reason you can't just say delta(s, u) is because you're not certain yet that it's actually the shortest path. Only at the end, when the algorithm 'converges', and the triangle inequality holds for all vertices, can you actually say that your d's (your estimates) are the deltas (shortest paths)
@@robje185 aah right, got it. Thanks!
@@robje185 but I think d(s,v)>delta(s,u)+w(u,v) can be correct if vertex u comes before v in topological order.because d(s,u) is the same as delta(s,u) as there is no subroute that can reach vertex u from vertex s going through any vertex that come after u in the topological order. am I right?
Instructor Solomon is watching there on the audience? (right-side of the video)
Yes, all the instructors attend every lecture. You can look for them in every video
@@annafebland4460 Interesting.
hey, i think i caught a slight mistake in the description. it says the instructor is erik demaine but isnt it jason ku?
either way, thank you so much for giving us free access to such great courses and lectures. im still in high school but watching these makes me even more excited to major in cs at uni. i dont completely understand everything but the instructors are so good ive binge watched them all in like two days.
im definitely coming back to this course when i start this topic at uni. ive got a feeling its going to be extremely helpful.
Thanks for your note! The description has been corrected.
thanks in name of all brazilian students.
This guy does not prepare for the lectures at all. He fumbles every 1.4 seconds and takes forever to construct a sentence and gets confused himself, mid-sentence. FOR ALL THOSE WATCHING: for this and the next three lectures on shortest paths, please go through the notes first and/or watch the 2011 version. Jason Ku really needs to improve his teaching skills.
I pity the students, Erik should take that chalk from Jason and start teaching
But for real doh. Jason needs to watch recordings of himself and practice not saying "right?" all the time
@@WeirdAlSuperFan I don't see the problem with saying "right?" , it's a way for him to see if everyone is following what he's saying or not.
@@Karim-nq1be The problem is 1) it's distracting af (and that's the main one), and 2) he says it so randomly that not only is nobody going to be nodding (especially in an auditorium where seeking feedback is meaningless), but it's obvious that he's more doing it as a coping mechanism to convince himself that he's actually teaching well when he isn't, so it's also annoying af
@@WeirdAlSuperFan interesting take that feedback is meaningless when you realize that the other instructors attend every lecture and correct mistakes when they occur