MIT 6.006 Introduction to Algorithms, Fall 2011 View the complete course: ocw.mit.edu/6-006F11 Instructor: Srini Devadas License: Creative Commons BY-NC-SA More information at ocw.mit.edu/terms More courses at ocw.mit.edu
Пікірлер: 105
@ChrisLeeX8 жыл бұрын
"Polynomial time is great, exponential time is bad, and infinite time gets you fired". Love it!
@magno51575 жыл бұрын
At Google, quadratic time is bad.
@hektor67665 жыл бұрын
If he hasn't convinced everyone already, there's further proof of what a great prof he is.
@sergeykholkhunov18882 жыл бұрын
01:52 graph requirements on the Bellman-Ford algorithm 04:28 review of generic shortest-path algorithm 06:40 first problem with generic shortest-path algorithm 07:45 second problem with generic shortest-path algorithm 11:29 Bellman-Ford 15:54 complexity of Bellman-Ford 18:02 correctness of Bellman-Ford 23:24 proof of the theorem (relaxation part) 30:22 proof of the corollary (check part) 33:35 questions 39:20 shortest-path vs longest-path
@user-td8zb9xo9k2 жыл бұрын
who are there watching these beautiful lectures in 2022 also? Because i feel it was much better way of explaining the things previously as compare to now where all the things are explained in ppts.
@proximush4 жыл бұрын
Amazing lecture. Some remarks: 1) In the proof of correctness (at 24:28) you don't need to pick a shortest path with the minimum number of edges. Any shortest path will do (always assuming that the graph has no negative cycles). 2) In the example (at 35:00) the professor affirms that you fix at the beginning an ordering of the edges and at each pass you relax the edges following that order. This is not strictly necessary for Bellman-Ford to work, as you can see from the proof of correctness. At each pass you can use any ordering of the edges. 3) This is more of a philosophical remark, connected to point 2), on how one could think about Bellman-Ford. Once one figures out that relaxing edges is the way to go to find shortest paths you need to choose in which order to relax them. This is nontrivial because the relax operation is non-commutative: if you first do relax(a,b) and then relax(b,c) you end up with different distances than if you do relax(b,c) and then relax(a,b). Bellman-Ford comes up with an ordering of the operations relax(a_i, b_i) such that if (s,v_1,v_2,..,,v_k) is a shortest path from s to v_k then the subsequence relax(s,v_1), relax(v_1,v_2), ..., relax(v_{k-1}, v_k) will appear for sure (in this order!), and this is enough.
@HR-ke1hv2 жыл бұрын
yeah bruh
@derekchen69759 жыл бұрын
You gotta love 42:40 when he catches an honest mistake, especially if you were able to see it first. The professor is brilliant, no doubt, but he is also human.
@takieddinemekhalfa81263 жыл бұрын
why are you so cute?
@mikechen31742 жыл бұрын
I love the part after the correction when the prof asked the other student, "and why did you say undefined?". "That's wrong." hahahah
@nikhilbelure5 жыл бұрын
it feels like im in class, learning and at the same time reading and writing comments , like talking with classmates , loved it !!
@bilalaytekin62823 жыл бұрын
It is fantastic how he runs a Bellman-Ford at 43:20.
@gregmakov26804 жыл бұрын
"5 minute university" sugestion is the point I like most in the lecture. Great, man!!
@thecuriousone1210 жыл бұрын
I love this teacher!
@ashutoshtiwari43983 жыл бұрын
Two key moments: 42:40 Finding his mistake and 43:20 Running Bellman Ford
@weiboliu60954 жыл бұрын
correctness proof of bellman ford algorithm starts at 18:08
@ms974 жыл бұрын
Clean explanations, easy to understand, thank you very much.
@MuhsinFatih5 жыл бұрын
what if you do 3 passes of E passes? 1 - first O(VE) pass, 2 - check pass (marking bad edges), 3 - another O(VE) pass skipping bad edges. I think that would give the simple shortest paths
@coding995 ай бұрын
46:05 the reason why Bellman-Ford can not find the reachable shortest "simple" path when there exist any negative cycles : you potentially go through negative cycle before you reach the destination, hence |V-1| passes might not be enough, which makes this NP-hard. Also, finding the longest path is equivalent to finding the shortest simple path.
@jan133710 жыл бұрын
free acapella concert!!!
@DarkLordAli957 жыл бұрын
I wanted to go, but had to study for the quiz he mentioned in class.... JK. I don't go to MIT :(
@saraconde91728 жыл бұрын
great lectures, help me a lot.
@kamanashisroy3 жыл бұрын
Think about coin change problem, how similar they are.
@IlkerDeligoz7 жыл бұрын
while negative cycles cause shortest path to be undefined, positive cycles do the same for longest path. so in a sense, if you negate everything and run B-F undefined result is still correct, isn't it?
@loganwishartcraig6 жыл бұрын
Yeah, that's what I thought too. I think he may have been referring to trying to find the longest *simple* path from s to v (i.e. not including cycles) which would be 6 in that example, but because of the cycle, would cause BF to return undefined.
@barsopiavivek8 жыл бұрын
26:22 how does only one relaxation give shortest path between two adjacent vertices. there could be v0->v2->v1 path which is shorter than v0->v1. thanks in advance
@paulsalvatore39358 жыл бұрын
I think in the case you mentioned it does give the shortest path between two adjacent vertices, those adjacent vertices being v0 and v2. It does not necessarily need to give the shortest path between all adjacent vertices but since every edge is explored, at least one will be the shortest path.
@Damian-cd2tj7 жыл бұрын
In first place, I think he should have say the first iteration of the for loop. Because each iteration makes |E| relaxations. So the second relaxation will be in the first iteration of the loop. But anyways, you have to run the entire for loop even if you wanna get the shortest path between 2 adjacent nodes. But at the end you'll figure out that if the shortest path between was v0->v1 then it was given in the first iteration of the for loop. If the shortest path was v0->v2->v1 then it was given in the second iteration. But you wouldn't know until you run the entire algorithm. It is a bit tricky because basically, after 5 iterations you will have all the shortest paths consisting of 6 nodes, and you will also have paths of 6 nodes that are not the shortest, but you won't know which one are which until you finish.
@harrypotter-el4lx3 жыл бұрын
it does not .it gives only current shortest path which will be updated once we relax edges coming out of v2 which wi;; be the shortest path of v0 to v1
@houidimohamedamin47473 жыл бұрын
because we already know that v0 -> v1 -> .... -> vk is a shortest path, that means all sub paths are also shortest paths, so v0 -> v1 is a shortest path from v0 to v1, there could be no shorter paths (otherwise v0 -> v1 -> .... -> vk won't be a shortest path from v0 to vk).
@fabiencedric66658 жыл бұрын
@10:59 How does dijkstra turn into exponential time?
@nitskrishna7 жыл бұрын
see @ 6:51 , he says for a graph if edges are selected wrongly and then complexcity in terms of number of vertices.
@theFlutterDeveloper10 жыл бұрын
In worst case every pair of vertices is connected by an edge. So the number of edges will be (n choose 2), which is n*(n-1)/2. That's about n^2 edges.
@AdityaPratapsingh91256 жыл бұрын
Can you please explain how would there be an exponential number of edges in the generic shortest path algorithm?
@user-hb9fr7wy9b6 жыл бұрын
I got the same question, why exponential?
@atrox76853 жыл бұрын
Are there other algorithms which could produce negative cycles?
@shuhbhm Жыл бұрын
any weighted general graph containing (-)ve weights can be solved using bellman-ford where as other algorithms are all specific case related which is outside the scope of 6.006
@xiangli95882 жыл бұрын
I don't understand what he is proving?
@bat_man11382 жыл бұрын
K
@AlexanderList8 жыл бұрын
What does -ve stand for?
@GopalSub8 жыл бұрын
+Alexander List Negative
@knowledge2memory10 жыл бұрын
perfect video - thanks for sharing ;-)
@seemaverma27911 жыл бұрын
excellent .....
@mostafasaadinasab63384 жыл бұрын
#besten #Episode Full Service#Vielen Vielen dank#bestimmt Liebe grüße und zu Videos#so#mit#
@MrRockashish8 жыл бұрын
can anyone tell me why negative weights are used?
@AnukulSangwan8 жыл бұрын
+Ashish Yadav There could be various situations. Consider this, if you travel from city A to city B you earn 50 rupees (+50), but if you travel from city B to city C you spend 20 rupees (-20).
@icaryslittle63703 жыл бұрын
An example would be traveling by boat up river ...
@nayankumarbarwa4317 Жыл бұрын
@@icaryslittle6370 Nice example
@sunitsingh91829 жыл бұрын
question .. why is the geeric algorithm's complexity O(2^n/2) ...somebody please help :)
@sunitsingh91829 жыл бұрын
R. S. Joshi ahh! bad bad typo :P thank you sir :) the proof makes the point so concrete!
@prodev74019 жыл бұрын
Suneet Singh is this the Efficient implementation because i think there is other solution with DP ?
@sunitsingh91829 жыл бұрын
Pro Dev bellman ford is kindda dynamic programming right? unlike dijkstra's greedy criterion, bellman ford relaxes all the edges and gauges shortest distance then... what is the other solution anyway??
@prodev74019 жыл бұрын
on this video this solution is effcient implementation for Save Space there is other solution the Original ;) kzbin.info/www/bejne/hYKYm6aYnaapla8 see min 49
@prodev74019 жыл бұрын
True ... ?
@kevinryzack57125 жыл бұрын
I've watched most of the lectures so far and this one is pretty bad. Recitation is definitely needed here. Viktor where are you!!
@jethsu95613 жыл бұрын
This doctor has mistaken concept of single source shortest path to shortest simple path.
@randalllionelkharkrang40473 жыл бұрын
i dont really understand the loop, where he loops v-1 times? can someone please help.
@PixelPulse1688 жыл бұрын
So, what exactly is difference between Dijkstra and Bellman-Ford?
@chengmingzhu4508 жыл бұрын
+Liang Luo different assumptions about the graph, different complexity, and of course, different algorithm.
@KRCPrice8 жыл бұрын
+Liang Luo Dijkstra won't work with negative edges.
@houssemdhiab73378 жыл бұрын
+Liang Luo the difference is that belman ford can solve a cycle where you have negative values
@alinradulescu706810 жыл бұрын
You came here for 11:33 - 15:20
@clapika99910 жыл бұрын
um why?
@alinradulescu706810 жыл бұрын
Toan Ngo The Bellman ford algorithm is explained in that interval. Since the video is named "Bellman Ford", this is what you searched for, and if you only want to understand how does it work, those 4 minutes are enough to understand it.
@clapika99910 жыл бұрын
Alin Radulescu those 4 minutes don't really show how it works - it's just the algorithm. Well, at least I won't truly understand B-F just by looking at the algorithm.
@syyamnoor97926 жыл бұрын
Not all heroes wear a cap
@user-hs7qg5tt8t5 жыл бұрын
hahahah
@nicholastan302710 жыл бұрын
im sorry, but why is E order V^2?
@siddhartha.saif256 жыл бұрын
In worst case every pair of vertices is connected by an edge. So the number of edges will be (n choose 2), which is n*(n-1)/2. That's about n^2 edges.
@loganwishartcraig6 жыл бұрын
With digraphs, I think it's just n*(n-1) since every node can be connected to every other node, resulting in two edges per node pair. (since E(u, v) != E(v, u) in a digraph). Think you're right for undirected graphs though. Still O(v^2) either way.
@MuhsinFatih5 жыл бұрын
@@loganwishartcraig That's not important. The point of analyzing complexity is understanding "in terms of what and how is your algorithm's time growing". For example, in Bellman-Ford, you are doing a check pass also, but you don't count the total complexity as O(VE + E), which technically is O((V+1)E), you say O(VE).
@rajawez45354 жыл бұрын
Think of adjacency matrix.
@patrickyue62648 жыл бұрын
Could any one please explain why is the exponential time? 7:03 Thanks
@chengmingzhu4508 жыл бұрын
+Pengqian Y see lecture 15
@user-eq4oy6bk5p8 жыл бұрын
Pathological selection of edge is pretty vague but It's clear that there is an exponential number of paths, where length of each path is at least 1 (or there is at least one edge). In particular, the number of paths from 1 to n-1 is 2^((n-1)/2) and we have this many choices of d[n-1]. In the worst case, it will try all of them and relax d[n-1] + (n-1, n)
@randalllionelkharkrang40473 жыл бұрын
at 4:44 , *throws hat in the air*
@kevinryzack57125 жыл бұрын
This guy doesn't explain why after relaxing each edge E, V-1 times, why we're guaranteed to have found the shortest path assuming no negative cycles. That seems to be a big point. At 28:49, he writes on the board, that after the second pass we get delta of (S, V2) because in second pass we relax (V1,V2)..But we relaxed (V1, V2) in all passes since in all passes we relax each edge, according to the algorithm. Kinda frustrating
@kevinryzack57125 жыл бұрын
This lecture has a much better explanation. The first 50 minutes goes over it: kzbin.info/www/bejne/jnqkgoWig9B9d9k Shai Simonson is great. He's not currently an MIT lecturer, but I believe he gave that lecture when he was working at MIT. Go figure.
@SchoolVideosGoHere4 жыл бұрын
@@kevinryzack5712 Thanks for the share; I had the same thought about that portion and was going to rewatch the video/read CLRS to see if I missed something (which I probably will do), but glad to see another lecture!
@DeepakLaxkar1472 жыл бұрын
@@kevinryzack5712 Had the same doubt. Went through a lot of resources and explanations, but couldn't find a better and intuitive explanation than this. Thanks for sharing.
@isbestlizard3 жыл бұрын
I don't think people should get to have trivial algoirthm named after themselves
@isbestlizard3 жыл бұрын
this is my algorithm for calculating the sum of a collection of numbers.. for i in collection: sum += i PUT ME IN TEXTBOOK
@theendurance3 жыл бұрын
@Lizard King its not about triviality, its about novelty. It was new, so it was recognized. Yours isn't new.
@timothygao94423 жыл бұрын
This is too edgy for me
@johnhopkins57942 жыл бұрын
Ha! I get it. It's a bit graphic for my tastes, but a good joke nonetheless.
@Ahmet76413 жыл бұрын
42:40 that was funny :D
@BrokenHeartanindo8 жыл бұрын
many things are not expalined in this video lecturer is giving short dialogs as if allpeople in the world is genius so please expalin every thing if you put something in youtube
@sailaminoak10 ай бұрын
i need to learn math
@lolno65277 жыл бұрын
MIT has an endowment of $13.182 billion, I wonder why it needs donations lol.
@DarkLordAli957 жыл бұрын
LMAO right??! that's what I always wonder whenever I hear that bit... you need donations? for realsies now???
@Saganist4206 жыл бұрын
We're talking about the American Educational system here... they can never have enough money. Maybe only american hospitals are more obsessed with money than private colleges.
@dylancutler19786 жыл бұрын
They're asking for donations for their open courseware, which is harder to get funding from the college administration. Why would the administration fund giving away the information for free? Open education is academia's last weapon against the commodification of information.
@BrokenHeartanindo8 жыл бұрын
see in ur comment box if every one can understand yoyr video no one will ever ask the question...bdw i had understand this from another book of indian mtech author...
@calyxwakefield35238 жыл бұрын
+Broken Heart first of you grammar is terrible and secondly you are not paying them for this lecture so stop talking trash, if you have doubts ask
@dhruvjoshi87444 жыл бұрын
@@calyxwakefield3523 exactly,he is like i want it free ,i will never donate, but will give my precious advice ...SOAB!
@andrewpersaud41446 жыл бұрын
i wish this guy taught all the videos. don't understand the white dude
@csl13844 жыл бұрын
Some of us prefer Eric (if saying the the "brown dude" is racist, isn't saying the "white dude" racist too, here is a question for you to meditate on), can't make all people happy all of the time.