Transcript
the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencourseware at ocw.mit.edu all right let's get started welcome back to 6046 uh today we start an exciting series of algorithms for graphs we've done a lot of data structures we're starting to get back into algorithms with uh dynamic programming last week and today in the next few lectures we're going to see lots of cool algorithms about graphs uh first a bit of recall we're starting with shortest paths which you've seen in 66 in the context of single Source shortest paths so typically like you do a Google Maps query you think of I want to go from A to B uh but what you solved in 66 was a harder problem which is I give you a point a here it's called s for the source uh I give you a source vertex in capital V is a set of all vertices capital E is set of all edges remember graph notation uh let's say it's a directed graph you've got Edge weights like the time it takes to Traverse each Road and you want to know how long does it take me to get from s to V for all V so this is uh from one given point to everywhere today we're going to solve a harder problem which is all pairs I want to go from all a to all B uh but what you saw in 66 was single Source where I just give you one of the vertices I want to know how to get to everywhere uh the reason you saw this version and not the A to B version is because the best way we know to solve a to B is to solve this problem so at least from a theory standpoint we don't know how to beat Dyer's algorithm and belman Ford's algorithm uh for uh the A to B problem so you get a little bit more than what you asked for so for the same price so let me remind you in a few different scenarios uh what algorithms we have and how long they take so the scenarios of Interest are the unweighted case a non- negative weighted case uh the general case arbitrary weights positive and negative and dags a cyclic graphs these are some interesting special cases and you should have seen in6 algorithms for each of them let's see if you remember so what's a good algorithm for single Source shortest path in an unweighted graph BFS good breath for search that takes how long V plus e good that's for for graphs V plus e is considered linear time that's how long it takes to represent the input so you got to look at the input most algorithms and BFS is optimal against that uh but we're going to start getting worse as we well uh for these two situations so for non- Negative Edge weights what do you use dyra oh everyone's awake this morning it's impressive uh and that takes how long this is a tricky question V log V plus e wow nice so the this answer kind of depends on which Heap structure you use but this is the best we know if you use uh a Fibonacci Heap which we don't actually cover but it's in the textbook uh you achieve log V for extract key and constant amortized for each uh decrease key operation so uh sorry this is for extract Min and this is for decreased key and so this is the best we know how to do with a dyra type approach if you use other heaps you get slightly worse maybe you get a log Factor here but this is good this is almost as good as V plus e uh for moderately dense graphs if e is bigger than V log V then these are the same uh but if your graph is sparse like e is order V then you lose a log Factor but hey it's just a log Factor not too bad we're going to get worse so for General weights what do you use Bellman Ford okay which takes how long ve it's the usual statement technically you should assume V is at least V for this bound to hold but that's uh the way to think of it so this is not nearly as good this is a lot slower um if you think of we can think of um two situations one is when e is Theta V so a very sparse graph like a tree or planer graph or something and we can think of when e is quadratic that's the dense case so uh here we get uh whatever uh V and v^ S for BFS uh for non- Negative Edge weights we get V log V in the sparse case and we get v^ s in the dense case and for Bellman Ford we get uh v^ s in the sparse case and V cubed in the dense case so this is like a V factor a linear Factor larger than non- negative Ed weights makes a huge difference uh and finally for ayylic graphs what do you do dynamic programming is one answer yeah uh that works in some sense all of these algorithms are or especially Bellman Ford is a dynamic program we'll see that a little bit uh another interpretation h topological sort and then Bellman Ford yep uh say one round of bellman Ford so Bellman Ford actually works really well if you know the order you should relax the edges and if in an a cylic graph you can do a topological sort meaning you visit all the vertices so that whenever you visit the right end point of an edge you've already visited the left end point if you do Bellman Ford in that order uh then you only have to do one pass and you're done whereas normally uh here you had to do it V times uh so the total cost of this is just uh linear so good good thing to remember especially on quizzes and so on if your graph is a cyclic you can achieve linear time uh but in the general case Bellman Ford is your answer for single Source now these are the best algorithms we know for each of these cases so I'm not going to improve them today uh you saw the the state of the art in6 but uh for all pair of shortest paths we can in some sense do better sort of so let me quickly Define the problem and then tell you all of the results we know and also the results we're going to cover today uh I didn't remind you of the Delta definition I want to go over this briefly so Delta of s comma V is the weight of the shortest path from s to V the weight is well defined even though there may be many shortest paths uh there's one best weight but there's some special cases it could be uh infinity if there's no path that's sort of by definition say well it's infinite cost to get if there's no path then we say there's an infinite weight one um and it could be minus infinity um in the presence of negative weight Cycles so I'll say if there's a negative weight cycle on the way if you can reach a negative weight cycle from s and then still get to V from there then the the the best way to get there is to go to that cycle loop around it infinitely many times and then go to V okay so um the algorithms you saw probably didn't actually compute correctly in this case they just said H negative weight cycle uh I don't know what to do but it's actually not that hard with a little bit more effort you can figure out where the negative infinities are we're not going to rely on that but I'm just throwing it out there to make this a well- defined definition once you have the shortest path weights you can also store parent pointers get the shortest path tree then you can actually find shortest paths um but again we're not going to talk about that here we'll focus on Computing Delta but with the usual techniques you saw in6 you can also reconstruct paths so for all pairs shortest paths we have a similar setup we have a directed graph ve and we have an edge weight function W in general could have negative weights and our goal is to find Delta of U comma V uh for all un and V okay uh single Source shortest paths is the sort of thing uh that you might want to do if you just give in a graph and you want to find a shortest path from A to B I said this is the best way we know how to do a to B essentially uh but all pair of shortest paths is what you might want to do if you're pre-processing if you're Google Maps and you want to be able to very quickly support shortest path queries between major cities then you may want to uh first compute all pair shortest paths for all major cities because Road networks don't change very much uh a large scale this is ignoring traffic and so on pre-compute this and then uh given a query uh of two vertices come in probably get a million queries a second you can very quickly know what the answer is and this is the basis for real world shortest paths typically you don't compute shortest paths from A to B every single time you you use way points along the way and you have pre-computed all pair of shortest paths between way points so that's the motivation um yeah I guess in some sense internet routing is another situation where at any moment you may need to know the shortest path to get to the the fewest hot path say to get to an Internet site you know the IP address you need to know where to go you don't need to know the whole path you need to know the next step uh but in some sense you're Computing all pair shortest paths that's a more Dynamic situation okay so uh here are the results we know for all pair shortest paths uh I think I'm going to cheat and reuse this board so uh same situations except I won't think about ayylic graphs here they're a little less interesting actually now I'm curious but I didn't intend to talk about ayylic uh and so the obvious thing to do to solve all pair shortest paths is just run the single Source algorithm V times once from each source Force so I could do V * breath for search V * dyra V * Bellman forward and now I just need to update my balance okay so ve becomes v^2 + V uh if you're a little bit clever or you assume E is at least V that becomes ve uh if I I run dyra V * I'm going to get v^2 log V plus v * e okay and if I run Bellman Ford V times I get v^2 e okay uh and over here everything's just going to increase by a v Factor so a little more intuitive is think about the sparse case I get v^2 uh v^2 log V and V cubed check that those match over there when E equals V and over here I get V cubed V cubed and V to the 4th okay so pretty boring so far um the interesting thing here is that we can beat the last result the last result which is the slowest one could take as long as V to the 4 time we can shave off a whole V Factor so better General case algorithm is called Johnson's algorithm that will be the last algorithm we cover today and it achieves this bound which is the same as running dyra V times uh so it's between v^2 log V and V cub and that's cool because this is the best algorithm we know for all pairs non- Negative Edge weight shortest paths just running dyar V times not very smart but it's the best thing we know how to do and what this says is even when we have Negative Edge weights actually we can achieve the same bound as running dyra this is a bit counterintuitive because in6 you're always told if you have Negative Edge weights can't use dyra turns out in the all pair shortest paths case you kind of can how could that be because uh this is a harder problem if you could solve all pair of shortest Paths of course you could solve single Source um and that's actually the luxury because it's a harder problem uh we have this ve term in the running time which lets us do things like run Bellman Ford once and running Bellman Ford once will let us run dyra V times that's that's the reason we can achieve this bound but we won't be seeing that for a while uh for starters I want to show you some connections between all pairs shortest paths and dynamic programming and matrix multiplication uh which turn out to give you for dense graphs we're just achieving V cubed in all situations so our first goal is going to be achieve to achieve VCB time uh for General Edge weights uh so we're going to first achieve this bound that will be a lot easier and then eventually we will achieve this bound so the uh the Floyd warshaw algorithm and some of these will get very close to V cubed all right so um we're going to start with our first approach to solving all pair shortus paths that is not using an existing single Source algorithm is dynamic programming someone mentioned that already it's a natural approach shortest paths is kind of dynamic programming in fact most dynamic programs you can convert to single Source shortest paths typically in a dag uh not all but a lot of them so uh we could try dynamic programming now uh I'm going to preach to you a little bit about my way of thinking about Dynamic programs if you've watched the6 ocw version you've seen the five five easy steps to dynamic programming so if and if you haven't this will be new otherwise a reminder first thing I like to think about in a dynamic program is what are the sub problems the second thing I like to think about is what am I guessing uh I'm going to guess some feature of the solution third thing is I want to write a recurrence relating sub problem Solutions then I'm BAS basically done but there's a couple wrapup things uh which I'm going to have to use another board for uh so number four is I need to check that I can actually resolve these sub problems in some order uh that's valid uh basically this is saying that the constraint graph on sub problems should be a cyclic because if there's a cycle in the constraint graph you take infinite time even if you memoize if you do infinite recursion bad news you'll never actually finish anything so you never actually write anything in the memo table so I want to make sure that it's a cyclic this is uh I mean this is really the same thing we're talking about in this erased row uh which is topological ordering personally I like to You could argue that it's a cyclic I like to just write down here's a topological order that's a nice proof that it's a cyclic if you write that down as four Loops then you actually have a bottom up DP if you just take the recurrence stick it inside the for Loop you're done uh which we'll do in a moment gu I need a row for that and finally you need to solve the original problem okay then there's analysis and so on but for specifying the algorithm these are the key things you you need to know the hard part is figuring out what the sub problem should be so that your DP becomes fast running time is going to be number of sub problems times time per sub problem for each sub problem usually we're going to want to guess some feature of the solution to that problem once we do that uh the recurrence becomes pretty trivial just for each guess you say what it should be uh so these are the really the hard two steps and then okay we check that it's a cyclic uh and we make sure that we can actually solve our original problem using one of the sub problems sometimes our original problems are some of the sub problems I think that will happen here but sometimes you need to do a little bit of post computation to get your answer all right so uh what am I going to do for sub problems well obviously I have a bunch of different problems involving uh pairs of vertices I want to find Delta of UV for all u and v that I erased uh but that's the problem so I want to know what is the weight of the shortest path from U to V uh if if I stop there and said that was my sub problems bad things are going to happen because I will end up there's no natural way to make this thing a cyclic if I want to solve U to V using I don't know U to X and then X to V something like that uh there's no way to get out of the infinite recursion Loop okay so I need to add more sub problems to add more features to my solution something that makes it so that when I try to solve my sub problem I reduce it to other s problems things get smaller and so that I can actually make progress so there actually two natural ways to do this I'll call them method one and Method two uh method two is actually Floyd warshaw but uh any suggestions on how we might do this this is a harder problem this is in some sense a kind of guessing but it's like I'm going to guess ahead of time that somehow there's an important feature of these shortest paths I'm going to parameterize by that and somehow it's going to get smaller yeah path with maximum in terms of right shortest path that uses at most given number of edges let's parameterize by how many edges I think I'll use M uh so using at most M edges very good so good I think it deserves a purple frisbee all right I'm getting better Slowly by the end of the semester I'll be pro at frisbee I should enter a competition um so uh this is of of course an additional restriction but uh at the end of the day the problem I want to solve is going to be essentially uh du UV uh let's say n minus one if I want a shortest path that does not repeat any vertices then certainly it has at most n minus one edges uh so in fact the claim would be that duv equals duv uh n I mean and so on if you go larger than n minus one it shouldn't help you if you know that your shortest paths are simple if you know that shortest paths don't repeat vertices so this would be if there are no negative weight Cycles if there are no negative weight Cycles then uh we know it never helps to repeat vertices so uh in that situation we would be done if we can solve this for all M now uh like catch how do we know there's no negative weight Cycles uh you know we could run Bellman Ford I guess that's a little tricky um because that only finds reachable negative weight Cycles in fact from this picture we will end up knowing whether there are negative weight Cycles uh so there will be no negative weight Cycles if and only if there's no negative uh diagonal entry say dvv n minus one so uh it turns out this algorithm we'll detect there's a negative weight cycle by finding that the distance from V to V is negative initially it's going to be zero if it turns out to be negative we know there's a negative white cycle with more work you could actually find all the reachable pairs and so on but I'm not going to worry I'm just going to say hey negative white cycle I'm going to throw my hands up in the air and give up for today okay uh cool so I can solve my original problem if I could solve these sub problems um and now things are easier because we can essentially assume in solving this problem that we've solved smaller sub problems for however we Define smaller that's what's given by this topological order obvious notion of smaller is smaller M presumably we want to write this with an m in terms of this with an M minus one or smaller uh so this gets to our guessing part how what feature of a shortest path could we guess that would make it one Edge shorter it's probably two good answers yeah the edge the the next Edge the next Edge which I guess you mean the first Edge sure you could guess the first Edge or you could guess the second Edge or no that would be harder or I mean the last Edge that would also work okay this is a harder one oh nope good thing there's students everywhere to catch it um cool so I'm going to guess the last Edge uh that's just how I written the notes but first Edge would also work fine so I'll call the last Edge X comma V we know we end by going into V so let's guess the vertex previous to it in the shortest path now of course we don't know what that edge is guessing just means try them all as you saw last time uh so now it's really easy to write the recurrence see if I can do it without looking at my notes so we've got uh du UV of M we want to write we want to find the shortest path so it's probably going to be a Min on the outside and we're going to consider the paths of the form uh D go from U to X using fewer edges right if if this is the last Edge then we use M minus one edges to get to X and then we follow the edge X comma V so I'll just add on the weight of the edge X Comm V if if x was the right answer this would be the cost to get from U Tov via X where X XV is the one a single edge at the very end we don't know what x should be so we're just going to do a for Loop over X for X in V so this is using python notation um and that will find the best answer done easy right once you know the sub problems are once you know what the guessing is uh basically I'm just adding and a Min and a for Loop to do the guessing so that's my recurrence except I should also have a base case here it's especially important uh so base case is going to be when m is the smallest so that let's say is zero what is the weight of getting somewhere using zero edges well uh typically it's going to be Infinity but there is an interesting situation uh where it's zero namely when uh U equals V okay there is a way to get from U to itself with zero edges and that cost zero um but anywhere else is going to cost infinity there's no path uh so this is sort of a definition uh I should say if it exists otherwise it's Infinity so then I get those Infinities but uh this is kind of important because maybe I actually use fewer than M edges I wrote less than equal to M here this is also less than equal to M um minus one edges here but in some sense I'm I'm including the case here where I just where x equals V so I just stay at V at the very end so it's uh because I have a zero here I'm implicitly including situation where actually uh I just use du UV uh M minus one that's in that Min here so it's important to get the base case right cool uh almost done I need an a cyclic ordering so uh as I said things get smaller when m is smaller so all that means is do the for Loop for M on the outside then do the for Loop for uh u and v for those it doesn't matter what order you do it as long as you've done all of m equals z before you do all of m equals 1 before you do all of m equals 2 so that's the nested for Loops that gives you the right order and so if I just take uh I guess I take this line and put it on the top and I take this line the induction uh of the currents put it inside the for Loops that is my bottom up DP okay I'm actually going to write it down explicitly here for kicks should I bother uh what the hell so first we do a four loop on on M then we're going to do the four loops on u and v uh now inside the for loop I I want to compute this men I could use this single line but I'm going to rewrite it slightly uh to connect this back to shortest paths uh because this type of statement should look familiar from dyra and belman Ford uh this is called a relaxation step okay it probably would look more familiar if I wrote here W of XV you could also write wxv that's an alternative uh for both of these probably should write the same way but in either case we call this a relaxation because uh it's kind of a technical reason but uh what we'd like to satisfy we know that shortest paths should satisfy the triangle inequality if you look there's three vertices involved here U V and X we're looking at the shortest path from U to V compared to shortest path from U to X and the shortest path from X to V certainly the shortest way to get from U to V should be less than or equal to the shortest path of U to X Plus X to V because one way to get from U to V is to go via X so this if condition uh would be a violation of the triangle inequality it means we definitely do not have the right distance estimates if duv is greater than ux plus XV okay so if it's greater we're going to set it equal because here we know a way to get from U to V via X we know that it's possible to do this assuming our D values are always uh upper bounds on reality uh then this will be an upper bound on the best way to get from U to V so this is clearly a valid thing to do relaxations are never bad if you start high uh these will always improve your shortest paths so you get better estimates and this is exactly what dyra and Bellman Ford did maybe with W instead of D but they're all about fixing the triangle inequality and in general in optimization there's this notion of if you have a constraint an inequality constraint like the triangle inequality and it's violated then you try to fix it by successive relaxation so that's where the term comes from doesn't really matter here but all of our shortest path algorithms are going to do relaxations all all the shortest path algorithms I know do uh relaxations so uh this is familiar but it's also doing the same thing here I've just expanded out the Min as a for Loop over X each time checking whether each successive entry is better than what I had already uh and if it is I update so in the end this will compute A Min more or less I I cheated also because I emitted the superscripts here if I put M here and M minus one here and one here it would be exactly the same algorithm I'm emitting all the superscripts because uh it can only help me relax relaxing more can only get better and if I was guaranteed correct over there I'll still be guaranteed correct over here you have to prove the invariant that you never uh relaxation is always safe if you start with upper bounds You always remain upper bounds you're doing at least the relaxations over there and so you will in the end compute the correct shortest path weights the advantage of that mainly is I save space and also it's simpler um so now I only need quadratic space if I had a superscript I need cubic space all right so I did a little simplification going from the the five-step process to here both would be polinomial time and space but this is a little bit little bit better but how how slow is this algorithm how long does it take yeah V cubed that would be great V to the fourth yeah good sadly we're not doing so great yet um still V to the 4th V to the fourth uh I guess I already knew how to do that was if I just run Bellman forward V times I already knew how to do V to the 4th so I haven't actually improved anything but at least you see it's it's all dynamic programming in there so n here is the size of V that's probably what you missed first time uh cool I admitted zero because zero was the base case that's done separately in a line that I didn't write but okay so that was dp1 time for DP two unless there are questions everyone clear so far yeah when do you do as opposed to oh yeah okay good um fair question why do I iterate over all vertices not just the incoming what I if I'm writing W of XV I could afford to just say just consider the incoming vertices and that would let me improve probably from V to the 4th to V cubed uh v s time E I think if you do the arithmetic right uh you could do that it would be better uh for dense grafts it's not going to matter for sparse grass it will def improve it will improve v s to e basically uh but we're going to do even better so I'm not going to try to optimize now but good question um when I say this at the moment if there is no Edge from X to V I'm defining I'm imagining that W of XV equals infinity so it will never that will never be the minimum choice to use a non-edge I should say that if there's no edge here I Define the weight to be Infinity that will just make algorithms cleaner to write but you could optimize it the way you said so where were you sorry yeah oh perfect okay other questions more frisbee practice no okay uh so that was dp1 let me do dp2 uh not yet sorry diversion diversion is matrix multiplication before I get to dp2 I want to talk about matrix multiplication uh yeah this is a cool connection it won't help us directly for shortest paths but still pretty good uh and it will help it'll solve another problem especially fast so shortest path is also closely linked to matrix multiplication a problem we've seen a couple of times first in the fft lecture and then in the uh randomization lecture for checking Matrix multiplies uh so you remember you're given to matrices A and B and you want to compute C = A * B uh you've seen sten's algorithm to do this uh there's also the the here A and B are square let's say so they're n byn product will be n byn so standard approach for this is n cubed with Sten I'm going to remember you can get n to the 2.87 and if you use copper Smith windrad you get 2.37 six and then if you use the new vasila Williams algorithm you get n the 2.37 28 and so on okay and that's the best algorithm we know now there's some evidence maybe you can get 2 plus Epsilon for any Epsilon turns out those aren't going to help us too much here um but what I want to show is that matrix multiplication is essentially doing this if you redefine what plus and dot mean if you redefine addition and multiplic talk about whether that's valid in a moment uh so remember what is matrix multiplication CI is do product of a row and a column so that's a i k with B KJ K = 1 to n okay now that sum looks a lot like that Min actually more like the way I wrote it over here uh with the D's instead of the W's uh this right X is the thing that's varying here so this is like uh a i k plus b KJ except I have plus here whereas I have times over here and I have a Min out here but I have a sum over here so sounds crazy but let's define be very confusing if I said define dot equals plus so I'm going to define a new world called Circle world so if I put a circle around a DOT what I mean is plus and if I put a circle around a plus what I mean is min okay so now if I put a circle around this dot I mean Circle everything so I'm going to circle the summation Circle this thing so then I get shortest paths okay crazy uh so all right I'm going to Define d to the MTH power uh I should probably Circle yeah whatever slightly different uh okay I wanted to find like three things at once so let me write them down and then talk about them so many infinities all right okay I guess write this too okay if I Define the ver suppose I number the vertices 1 through n okay just assume all vertices are an integer between one and N so then I can actually Express things in a matrix namely the the weight Matrix this kind of defines the graph especially if I say w j is infinity if there is no Edge then this is the Matrix of all pairwise weights Edge weights for every I and J I have a weight of i j that gives me a matrix once I set V to be 1 through n now I'm also defining this distance estimate Matrix so remember we defined du UVM I'm going to now call it D JM because the vertices are integers that is the weight of the shortest path using at most M edges if I Define it that way then I can put it into a matrix just for all pairs of vertices i j what is the distance shortest pathway that uses at most M edges that gives you a m a matrix D parenthesis M okay uh then I claim that if I take Circle product between D of M minus1 and w that is exactly what's Happening Here If you stare at it long enough this is the inner product between row U of D to the m minus one and column V of w and that's exactly what this circle product will compute so this is the DP but when you look at that that statement that's saying that D to the parenthesis m is really w to the circle power M right this is a definition in some sense of of power of exponentiation using Circle product so when I Circle the exponent that means I'm doing Circle exponentiation and circle L okay uh okay so far so this is um this is circle land right uh so you might say well then I should compute these products using matrix multiplication now just to see how how good we're doing um if I execute this operation you know n times because I have to get to D to the N minus one so it's basically D to the N um if I do this product n times and for each one of them I spend n cubed time then I get an N the four algorithm okay same algorithm in fact exactly the same algorithm I've just expressed it in this new language okay there are two ideas on the table though one is maybe I could use a better matrix multiplication algorithm Let's uh sh that for a moment the other possibility is well maybe I can exponentiate faster than multiplying by myself n times or multiplying by w n times how should I do it repeated squaring good you've seen that probably in6 repeated squaring idea is we take uh to compute W well okay I take W to the 0 I multiply it by W the 0 that's uh sorry Circle Z that's this thing oh that seems weird let's start with one one seems better not going to get much If I multiply that by itself I should get exactly the same Matrix so I take the circle product between W to the 1 W to the one that gives me W 2 and then I take W 2 uh time W 2 everything circled I get W 4 oh cool I doubled my exponent with one multiplication if I take W 4 by W 4 I get W to the 8 and so on my goal is to get to n so I have to do this log n Times log n squaring operations each squaring operation is an N cubed thing uh so this is repeated squaring and I get V cubed log V finally an improvement so we went from V to the four which was in this in the dense case the same performance as Bellman Ford running at V times but now in the dense case I'm getting V Cub log V which is actually pretty good uh it's not quite V cubed but close all right I'm pointing at V Cube this is actually the one result that is not optimal this is the one we want to improve okay but we're kind of we're in this space right now we're getting close to as good as this algorithm the Johnson's algorithm but we still have a log V Factor so this is great use just by translating into matrix multiplication now technically you have to check that repeated squaring actually gives you the same result uh basically this works because uh products are associative Circle products of matrices are associative which works because Circle land is a semi- ring if you want the abstract algebra a ring is something that you wear on your finger no a ring is uh an algebra where you define plus and times and you have distributivity semi- ring uh plus there's no minus because Min has no inverse there's no way from the Min to recompute the arguments right no matter what you apply to it you can't you've lost information so that's the semi- ring normally you have a minus uh but semi- ring is enough for repeated squaring to give you the right answer however semi ring is not enough for all these fancy algorithms so if you look at stren's algorithm the one you've seen it uses minus there's no way to get around that as far as we know so if you have no minus cubed is the best we know how to do so sadly we cannot improve Beyond this with this technique sucks but that's life uh however we can do something if we just change the problem there is another problem which this is the best way to do so let me brief tell you about that problem it's called transitive closure transitive closure is I just want to know is there a path from I to J so it's going to be one if there exists a path from I to J and it's going to be zero otherwise okay this is kind of like uh I guess it's kind of like if you set all the weights to zero or Infinity then either there's going to be a zero way path or there's no path meaning there's an infinite we path so it's not quite the same here I want one and zero i' I flipped it used to be this was infinity and this was Zero but this is one saying there is a path from I to J zero otherwise if I write it this way and then I think about what I need to do here it isn't still it is still in some sense plus and Min but not really because I just want to know is there a path so if I have a way to get there and a way to get there instead of adding up those values really I'm taking some other operator so I want to know or yeah exactly who said or yeah all right tough one close close close uh so here we have basically uh Circle product is or and circle sum is and okay I mean plus and and Min would work but it's a little bit nicer over here so uh sorry it's the other way around I think yeah it's definitely Boolean we want to know there is a way to get to X and then from X to where we're going that's an and and then to get a path in general uh it has to work for some X so that's the or and this is a ring and once you're ring you have negation uh you can apply basova Williams and you'll solve this problem in N to the 2.
3728 and if I just make a little change in the dot dot dot uh I can absorb the log so you you could put a log n here and it's log n if you get the exponent exactly right but if you just tweak the exponent by 0 one that's bigger than log n so we usually emit the log there cool uh transitive closure so it's a problem you didn't know you wanted to solve but it is is actually a common problem and this is the best way we know how to solve it for dense graphs okay this will beat it it beats you know V cubed this is this is the algorithm we're aiming for for dense graphs for sparse graphs we can do better but for dense graphs uh this is better okay all right finally we get to go to dynamic programming number two also known as the Floyd warshaw algorithm so we had this DP in V to the 4th uh if we forget about transitive closure we've now are down to V cubed log V our next goal is to achieve V cubed no log V so let's do that so again I'm going to express it in my five steps first step is what are the sub problems and this is the key difference and the key Insight uh for Floyd warshaw is to redefine the DJ problems to avoid conflict I'm going to call them CI J or in this case CU UV because here the matrix product view will not work I think yeah won't work so it's totally different universe I'm still going to assume that my vertices are numbered 1 through n and now the idea is first I'm going to think about the graph formed by the vertices 1 through K roughly and I want to know for every vertex U and every vertex V what is the shortest path from U to V or the weight of the shortest path from U to V that only uses intermediate vertices from 1 through K so actually u and v might not be they might be larger than K but I want all the vertices in the path to be one through K this is a different way to slice up my space and it's the right way this is going to do a factor of n better uh it turns out and that's just an Insight you get from trying all the DPS you could think of and eventually Floyd and warshaw found this one um I think in the 70s so it was easier back then to get a new result but um but it's this I mean this is very clever so very cool idea so now the question is what should I guess before I guess what the last Edge was that's not going to be so useful here can anyone think of a a different thing to guess we're trying to solve this problem where I get to use vertices 1 through K and presumably I want to use sub problems that involve smaller K that say involve vertices 1 through K minus one so vertex K is relevant what should I guess about vertex K yeah is the you want to guess vertex K is the I intermediate vertex that would work but I would need to parameterize by I here and I lose another factor of n if I do that so I'd like to avoid that that that is a good idea yeah you're going to guess that I visit K and then uh go to where I'm trying to go okay that's that's not a uh okay that's a statement uh but to guess I should have multiple choices what's my other choice ah yes so either I use vertex K or I don't that's the guess uh is K in the path at all from U to V so that's uh a weaker thing than saying K is at position I in the path here I'm just saying is K in the path at all and that's nice because as you say I already know how to get there without using K because that's C UV K minus one and then I just also have to consider the situation where I go to k and then I leave so the recurrence is going to be uh CU UV K is min of two things one is when K is not in the path that's CU UV K minus1 and the other option is that I go to x first or sorry I go to k first it used to be X now I've renamed it to K I don't know why uh K minus one and then I go from K to V K minus one that's it Min of two things before I was taking the Min of N Things before there are n choices for my guess now there are two choices for my guess number of sub problems is the same still V cubed but the guessing part and the recurrence part is now constant time instead of linear time so I'm now V Cub time progress okay this is pretty cool the old DP led us to this world of matrix multiplication that's why I covered it uh this new DP is just a different way of thinking about it turns out to be faster just by log Factor but a little bit faster uh I need some base cases CUV of zero is going to be now it's the weight of the edge UV uh it's a different base case before it was using zero edges now it's not using any intermediate vertices so that's how the weights come into the picture because actually there are no weights of edges up here so that's a little weird the only place the weights come in is in the when k equals zero okay this is in some sense still relaxation but it's a little bit weirder little bit different order uh I mean the key thing here is because we because the way we set up the this these sub problems with the intermediate vertices we know K is the only vertex in question before it's like well I don't know where you go at the end but now we it's we know that either K is in there or it's not and in each case we can compute it uh using smaller sub problems and so we save that linear Factor only fors or does also this is for directed graphs y Uh u and v are ordered here and this is the weight from U to V will look work just as well uh it's probably a little bit instructive to write this down as nested for Loops again why not because then you'll see it's just relaxation again so uh I'll even write the base case here because it's very simple we're doing K in order let's say uh these are really the same kinds of for Loops but I'll write them slightly differently because here we care about the order slightly uh here we we do care about the order here here we don't care about the order vertices and all we're saying is almost exactly the same code as before this is again just a relaxation step we're just relaxing different edges in different orders uh basically because K is involved in here we do that for k equals 1 then for k equals 2 and so on uh but in the end it's just relaxations so you can use that to prove that this actually computes the right shortest paths I won't do that here uh but clearly cubic time instead of cortic pretty cool that's Floyd warshaw it's very simple and so a lot of people if you need to solve all pair shortest paths in dense graphs this is the best we know how to do so this is what you should Implement it's like five lines of code uh and you achieve this bound but for sparse scrafts we can do better and the rest of lecture is going to be about Johnson's algorithm where for Spar SC we're going to get closer to quadratic time we're going to match running dyra uh and it's it's v^2 log V plus e time V sorry uh so when e is small that's going to be close to quadratic when e is Big that's going to be cubic again so will never be worse than this flood warell algorithm but if for Spar graps it's better okay Johnson's algorithm it's going to make some joke about Johnson and Johnson but I will pass uh so Johnson's algorithm I mean DP is five steps but Johnson's Algin is only three steps clearly simpler it's actually much more complicated but uh it's all about what the steps are so here's the crazy idea in Johnson's algorithm we're going to change the weights on the edges and to do that we're going to uh assign weights to vertices we're going to choose a function H think of it as a height function I guess that Maps vertices to real numbers and then we're gonna Define w subh of UV this is a new way to think about Edge weights that depends on H it's defined in a simple way it's the old Edge weight uh plus h of U minus h of V you could Define it the other way but uh it's better to be consistent here so this is a way to tweak Edge weights for every Edge you this is for directed graphs clearly uh for U you is the beginning the head of the I don't know if it's the head or the tail the beginning of the edge V is the end of the edge I'm going to add on the weight the height of H and subtract off the height of V okay why because that's the definition I want this to be greater than or equal to zero that's the such that I want to assign a function H so that these new weights are all greater than equal to zero this is for all u and v why would I do that to use dyra instead of bman Fort exactly so that's step two run dyra on uh I guess the old the usual graph but now this new weight function W subh if all the weights are non- negative I can run dyra uh so this will give me what I call the shortest path subh of U comma V for all u and v it doesn't give me the actual shortest path weights I want it gives me the shortest path weights using this wh but I claim it's almost the same I claim that this reweighting preserves which paths are shortest because well so in particular I claim uh that Delta of UV is Delta subh of UV uh should be the other way minus h of U plus h of V okay if uh if this was a single edge you can see I'm just canceling off these terms but in fact I claim for a whole path every path from U to V gets changed by exactly the same amount so this is a claim about the shortest path but in fact I claim for every every path from U to V shortest or not uh if I measure it in in regular weights W versus weights W subh the only difference is this fixed amount which depends only on u and v does not depend on the path and therefore which paths are shortest are preserved and so when we compute these shortest path weights we can translate them back to what they should be in the in the original waiting function and furthermore if you have parent pointers and you actually find the paths the paths will be the same shortest paths will be the same okay so let's prove that claim it's actually really simple so let's uh let's look at a path from U to V so I'm going to label the vertices along the path v0 is going to be U that's the first one uh then V1 then V2 and so on let's say path is length K uh and K is VK is V okay that's a just a generic path from U to V and now I want to compute the uh w subh of that path excuse me so uh the weight of a path is just the sum of the weights to the edges so I can write this as a sum from I = 1 to K of w subh of VI minus one comma VI I think that works got to be careful not to get the indices wrong okay now W subh is defined to be this thing w plus h of U minus h of V so this is the sum I = 1 to K of w vi-1 VI I uh plus plus plus h of VI minus one minus h of VI what does the sum do telescope so success this VI is going to this negative h of VI is going to cancel with the plus h of VI minus one in the next term except for the very first one and the very last one so this is going to be this sum which is just the weight of the path according to regular weight function uh plus h of V 0 minus h of v k uh and that is just the way to the path plus h of U minus h of v i get it right nope yes uh but it's not it's opposite of what I claimed so oh right because it's the other side good this has h on the right hand side this has not h on the left hand side but here I have H on the left hand side and not h on the right hand side okay so if I flip it around if I take these two terms put them on the left hand side then I get this with the right side cool self-consistent okay so uh this was talking about an arbitrary path and so this is proving the stronger thing I said that every path gets lengthened by this function which is purely a function of the end points so in particular that means the shortest path in W land will still be the shortest path in W subh land slightly less cool name than Circle land but oh well um all right so this means shortest paths are preserved shortest paths are still shortest and therefore if I look at the Delta function which is about the shortest path weights uh this claim holds okay so that's the proof of the claim cool there's one gaping problem with this algorithm uh which is how in the world do you find this H if we could find H then we know we can run dyra and we can do this thing uh now and dyra is going to cost the ve plus v^2 log V uh I say it but we run V * dyra right we run it V * that's going to take v^2 log V plus v to do uh this is just going to take quadratic time v^ squ to update all the weights update all the Delta functions the the missing step is how do we find this weight function I claim this problem of finding H that has this property is very closely related to shortest paths it's weird but we're going to use shortest paths to solve shortest paths so let's do it step one finding H what I want to do is I want to have W of UV let me just copy that down plus h of U plus h of V to be greater or equal to zero whoops minus I'm going to put the H's onto the right hand side and then flip it all around so this is like saying h of V minus h of U is less than or equal to W of UV okay for all u and v this is a problem we want to solve right W's are given H's are unknowns this is called a system of difference constraints if you've heard about uh linear programming for example this is a special case of linear programming don't worry if you haven't heard because this is an easy special case we're going to solve it much faster than we know how to solve linear programs uh it's a particular kind of thing this is actually a useful problem you can think of there these are maybe times that various events happen and these are constraints about pairs of them says well uh the start time of this event minus the end time of that event should be less than or equal to uh 1 second you can use this to do uh temporal programming if you could solve these systems we're going to solve these systems when they have a solution they don't always have a solution uh which is a bit weird because we're relying on them always having a solution how could that be negative weight Cycles this is all going to work when we don't have negative weight cycles and that's exactly going to be the case when the this system of difference constraints has no solution so uh let me show you that in a couple of steps first theorem is that if the graph VW has a negative weight cycle then that system has no solution no solution to the difference constraints this is going to be again a easy proof kind of similar to the last one actually so uh consider a negative weight cycle uh let's call it v0 to V1 to V2 to VK back to v0 so it's claim is the sum of these weights is negative and now I'm just going to write down these constraints which are supposed to have a solution or maybe they won't so if it has a solution then this must be true where u and v are plugged in to be uh VI and VI minus one because those are all edges so uh I'm going to write h of V1 minus h of V 0 is less than or equal to W of v0 w V1 and then h of V2 minus h of V2 V1 is L equal to W of V1 V2 repeat that K times going to get H of VK minus h of VK minus one and then the last one the wraparound h of v0 minus h of VK W of v i get it right yeah VK v0 what do I do with these inequalities sum them time for a Goodwill Hunting moment uh you remember I hope you've all seen Goodwill Hunting I don't have a janitor here so I have to you know do all the cancels by hand uh and then this so I end up with zero at the bottom everything cancels and then over here I have uh less than or equal to the weight of the whole cycle I'm just adding up the weight of the cycle I didn't give the cycle a name call it C now the cycle has negative weight so this is less than zero strictly less than zero and so we're saying that 0 is strictly less than zero that's not true so that means there's no way to get all of these constraints simultaneously true okay proof by a contradiction so that establishes a connection in the direction we don't want it what we want is the converse which is if there's no negative weight cycle then there is a solution luckily that is also true but this is a little easier to see so now we do the other half okay all right and this will I it's going to be a constructive proof so we're going to actually know how to solve this problem an algorithm so it's going to be uh there's a negative white cycle if and only if there's no solution so in particular the case we care about is if there's no negative white cycle then there is a solution we kind of care about both but uh this is the more practical Direction so let's prove it you can already see you've seen that there's a connection in negative weight Cycles now I'm going to show there's a real connection to shortest paths negative weight Cycles are just kind of you know a symptom of of uh shortest paths being involved so now we're going to use shortest paths um suppose we have some graph I'm going to draw a simple little graph with weights what I'd like to do is compute shortest paths from a single Source in this graph the question is which source because none of the vertices I guess I guess in this case this would be a pretty good source because it can reach from here I can get to every node but in general that maybe there's another vertex here uh I draw a more complicated picture it could be there's no one vertex that can reach all the others right for example maybe the graph is disconnected that's a good example so there's no single source that can reach everywhere I really want to reach everywhere so what am I going to do add a new source call it s I'm going to add an edge to every other vertex now I can get everywhere from s okay uh what are the weights zero zero sounds good I don't want to change the weights in some sense so I put zero and add zero to everything it's not going to change much uh now notice I add no Cycles to the graph so if there were no negative weight Cycles before still no negative weight Cycles because the Cycles are the same as they were before but now from S I can reach everywhere if there's no negative weight cycles that means there's a well- defined finite value for Delta of s comma V for all V and that is H what it's crazy man all right so we add s to V we're going to add uh s comma V to e for all V that's the old V and we're going to set the weight of s comma V to be zero for all V okay that's what I just did and so now uh Delta of s comma V is finite for all V um it's not plus infinity because I know there is it's got to be less than zero right I can get from s to everywhere uh so it's less than positive Infinity it's also not negative Infinity because I've assumed there's no negative weight Cycles anywhere so I'm going to let h of V be Delta of SV and I claim that just works magically it's insane every time I see it's like got to be crazy man crazy but correct that's Johnson it's like you just pray that this happens and it works why would it happen why why would it be that uh what do we want to say w of UV plus h of U minus h of V we want this to be greater than or equal to zero I guess I I had already Rewritten it this way okay neither way it's the right way so uh it doesn't matter so let's see we have weight of UV we have the shortest path from s to U and we have the the shortest pathway from s to V want that to be greater than equal to zero why uh put this over there and I get Delta of SV is less than equal to Delta of su plus W of UV which is triangle inequality which is true it turns out this thing we've been staring at for so long is actually just triangle inequality so of course we want to compute shortest paths because shortest paths satisfy triangle inequality the whole name of the game in shortest paths is to find a place where you don't satisfy triangle inequality and fix it so if it makes sense if it's that if that's possible to do belman Ford will do it so how are we going to do step one we're going to run belman Ford once we're going to add this Source vertex so that there is a clear source to run Bellman Ford from and then run Bellman Ford from there only that will give us a weight function for the vertices namely how how long does it take to get from s to those vertices those weights will actually all be negative but then we're going to modify all the edge weights according to this formula which negates some of them so some of them are going to go up some of them are going to go down it's kind of weird but when we're done all of the weights will be non- negative because we had triangle inequality and now we can run dyra from every vertex so it's like we bootstrap a little bit we run Bellman Ford once because we know it handles negative weights it will also tell us if there are any negative weight Cycles that's why we want uh this theorem maybe belman for says I can't satisfy triangle inequality because there's a negative weight cycle I don't know what to do then we know well actually then there was no solution okay that's kind of interesting um but and then we'll have to deal with those shortest paths sorry deal with those negative white Cycles I won't cover how to do that here but you can uh and otherwise there's no negative white Cycles then Bellman Ford finds valid H then we plug that H into here then we have non- negative weights so in ve time we've reduced to the negative the non- negative all pair shortest paths and then we run dyra V times then we get almost our answers but we have to modify them to get back the correct weights on our shortest paths and so we computed shortest paths in V squ log V plus ve because this is how much dyra costs and because Bellman Ford takes less time we're good that's the magic and that's all pair of shortest paths