17_shortest_paths.md

　　We're going to talk about shortest paths for three lectures(我们大概要讲它三次课).Today will be Shortest Paths one(今天讲最短路径第一部).Shortest paths are sort of an application of dynamic programming(最短路径算法是一种动态规划的应用),which we saw last week, and greedy algorithm,which we also saw last week.So, we're going to build that and get some pretty interesting(我们一会要实现它 用一些很有趣的算法)algorithms for an important problem, which is(来解决一些重要的问题 例如)how to get from Alderon to(如果从奥德隆出发),Cambridge as quickly as possible(怎么才能最快到剑桥).OK, when you live in a graph(假设是在地图上走的话).So, there's geometric shortest paths which is a little bit harder(几何学上有几种最短路径 那比较复杂).Here, we're just going to look at shortest paths in graphs(但这里 我们只关注图的最短路径).Now, hopefully you all know what a path in a graph is(我想你们都应该知道 图的路径是什么了).But, so, very quick review in particular(但还是简单地回顾下)because we're going to be looking at weighted graphs(因为我们准备研究加权的图).So, the usual setup: suppose we have directed graph, G,(那一般前提是 假设我们有个有向图G)have some vertices, some edges(有一些顶点 一些边).We have edge weights, make it a little more interesting(已知边的权重 这会使得图更加有趣).So, this is just a real number on each edge(权重就是每条边上的一个实数).So, edge weights are usually given by function, w(权重可以用函数W来表示).For every edge, you get a real number(对于每条边 都有一个实数). 　　We're going to use some simple notation for paths(我们会用一些简单的符号来表示路径)called a path, p, starts at some vertex(比如路径p 起点是某个顶点),and it goes to some other vertex, and so on(经过另一个顶点 等等).Say the last vertex is v_k, and(最后一个顶点是v_k)each of these should be a directed edge in the digraph(这些都是有向图里面的有向边).So, this is a directed path(所以 这是一条有向的路径).Path to respect edges in here(它由对应的这些边组成).And, we'll say that the weight of such a path(然后 一条路径的总权值)is just the sum of the weights of the edges along the path(等于路径上的各边得权值的总和).And, we'll call that w(p)(我们令此为w(p)).This is sum, i equals one to k-1 of w(v_i, v_(i+1))plus one.OK, so just to rub it in(好的 把它画出来).and in particular, how general this can be(那在这里 它一般会是这个样子),we have some path, it starts at some vertex(我们有一条路径 它从某个顶点开始),there's some edge weights along the way(它经过的每条边上有一些权值).This is some arbitrary path in the graph(这代表图里任意一条路径),in some hypothetical graph(在某一副假想图里的路径).OK, this is mainly to point out that(好 这里主要想讲的是)some of the edge weights could be negative(有些边的权值可能是负值).Some of them could be zero(也有一些可能等于0).This sum here is minus two(这里的和等于-2).And, presumably, the graph is much bigger than this(这幅图可能比这儿要大得多).This is just one path in the graph(这只是图里面的一条路径).We're Usually thingking about simple paths that can't repeat a vertext(我们通常考虑的简单路径不会重复经过一个顶点).But, sometimes we allow that(但有时候 我们又允许有这种情况). 　　And then, what we care about is the shortest path(然后 我们关心的是最短的路径).or a Shortest path. Again, this may not be unique(或者是某一条最短路径 因为可能不止一条),but we'll still usually call it the shortest path(但我们通常会称之为最短路径).So, we want the shortest path from some A to some B(我们想求从A点到B点的最短路径).Or, we'll call the vertices u and v(我们设这两点为u和v).And we want this to be some path of minimum possible weight(我们想让路径的总权值尽可能地小),subject to starting at u, and going to v(使得从u到v的路径最短).OK, so that's what we're looking for(好的 这就是我们想要的).In general, give you a vertex u, give you a vertex, v(一般来说 给你起点u和终点v),find a shortest path as quickly as possible(如果要最快地找出最短路径).What's a good algorithm for that(有什么好的算法)?That's the topic for the next three lectures(这就是接下来三次课要讲的内容).We'll usually think about a slightly simpler problem(我们通常会思考一个简单一点的问题),which is just computing the weight of that path(就是如何计算路径的权值),which is essentially computing the distance from A to B(说白了就是计算从A到B的距离).So, we'll call this the shortest path weight from u to v(我们把从u到v的最短路径的权值).And, we'll denote it by delta of(u,v), delta(用(u,v)来表示 这个小写的).So, I mean, it's the weight of the shortest path(那么 它等于最短路径的权值),or a weight of every shortest path(或者说 每条最短路径的权值).Or, in other words(换句话说),it's the Min over the weight of each path from u to v(它等于所有从u到v的路径中的最小值).So, p here is a path(这里的p是一条路径).OK, so you just consider(你只要这么想),there could be a lot of different paths(这里可能有许多不同的路径).There could, in principle, be infinitely many(理论上 这有无数条路径),if you're allowed to repeat vertices(如果允许重复经过顶点的话).You look at all those paths hypothetically(假设 你把所有这些路径都算一遍).You take the minimum weight(然后取最小的权值). 　　My next question was going to be(我的下一个问题是),when do shortest paths not exist(什么时候 这条最短路径会不存在)?And you've hit upon one version(你们已经遇到一次这种情况了),which is when you have negative edge weights(就是出现负权值的边的时候).So, in principle, when you have negative edge weights(原则上 当你有负值的边时),some shortest paths may not exist(最短路径就可能不存在)OK, in particular, if I have two vertices, u and v(但实际上 如果我有两个顶点u和v),and I have negative edge weights(而其中又有带负值的边).But when specifically won't I have a(但什么情况下 才会真正地...)single shortest path from u to v(没有一条从u到v的最短路径)?So, if I can find the cycle somewhere along here(如果我在某处找到了一个环) whose total weight, say,(它总的权值是)the sum of all the weights of these images is negative(这些权值的总和是负的),then I get there, I go around as many times as I want(如果我在这里 不断地跑这个环).I keep decreasing the weight(这样总权值就会不断减少)because the weight is negative(因为这条环是负的).I decrease it by some fixed amount(我每走一次就减一个定值),and then I can go to v(然后我再走到v).So, as long as there is a negative weights cycle reachable(只要是在从u到v的路径中)from u that can also reach v(经过了一个负环),then there's no shortest path(这样便不存在最短路径)because if I take any particular path(因为无论我选择哪条路径),I can make it shorter by going around a couple more times(我都可以不断走负环来变得更短).So, in some sense, this is not really a minimum(所以在某种程度上 这不是真的最小值).It's more like an infimum for those who(对于某些数学痴来说)who like to get fancy about such things(这更应该说是一个下确界).But we'll just say that delta of (u,v)(但在这里 我们会记delta(u,v))is minus infinity in this case(为负无穷).There's a negative weights cycle from u to v(因为u和v之间有一个负环).So, that's one case we have to worry about in some sense(所以 这种情况是我们需要注意的).But, as long as there are no negative weight cycles(然而 只要没有负环的话).delta of (u,v)will be something bigger than minus infinity(delta 就会是大于负无穷的值),some finite...bounded below by some finite value(有一个有限的...有一个有限的下界)even if you could have negative weights(就算你有负权的边),but still no negative weights cycle(但没有形成负环的话)for example, there might not be any cycles in your graph(比如说 你的图里没有任何的环).So that's still interesting(那这问题就还值得探讨).And, I guess it's useful to note that(而且 我觉得这样想会更好懂)you can get from A to B in negative infinite time(如果你从A到B花的时间是负无穷).It's great, it's time travel(恭喜你 你穿越了),if the weights happen that correspond to time(假如权值表示的是时间的话).But when else might shortest paths not exist(还有什么情况下最短路径不存在)?So,there's one case,but there's another, simpler case(但还有另一种简单的情况). 　　It's not connected. There might not be any path from u to v(顶点没有连起来 从u到v可能一条路径都没有).This set might be empty(路径集合为空).There may be no path from u to v(可能一条从u到v的路径都没有).Here we have to define what happens(这里我们要下一个定义),and here, we'll say it's infinity(当u到v之间没有路径时)if there's no path from u to v(我们设它为无穷大).So, there are these exceptional cases(以上就是特殊情况)plus infinity and minus infinity which are pretty intuitive(一个正无穷 一个负无穷 显而易见),because it takes a really long time(因为它真的要花超长的时间)to get from u to v if there's no path there(来从u到达v).You can't get there from here.OK, but that's the definition(好的 定义完了).Most of the time, this is the case we care about, of course(当然 在很多时候 我们都留意这些情况).Usually this is a finite set(但通常它是一个有限集).OK, good, so that's the definition(好的 这是我们给的定义).Now let me tell you(现在我说). We're going to get a few basic structural properties(接下来 我们要学习一些)about shortest paths that will allow us to(最短路径的基本特征)obtain good algorithms finding these paths when they exist(以此来构造好的算法 找出存在的最短路径).And, in particular(特别是),we want to use ideas from dynamic programming(我们想用上动态规划的思想).So, if I want to use dynamic programming(所以 如果我想用到动态规划)to solve shortest paths(来解决最短路径问题),what do I need to establish(我要确定些什么)?What's the first thing I should check(我首先要注意的是什么)?You've all implemented dynamic programming by now(你们都试过写动态规划),so should make complete sense hopefully(应该都有一个全面的理解),at least more sense than it did a couple of weeks ago(至少比前几周没接触过的时候要好),last week, when we learned it(上一周 我们都学过了).Dynamic programming is something that grows on you(动态规划的学习是要积累的).Every year I think I understand it better than the previous year(每一年我都觉得 自己对它有了更好的理解).But, in particular(但有一点),when you learned dynamic programming in this class(当你在课堂上学习了动态规划),there is this nice key property that you should check(你们要注意到一个关键的性质).Yeah?Optimal substructure: good(什么？最优子结构 有见地).This is the phrase you should keep in mind(这个短语你们要牢记).It's not really enough for dynamic programming to be(虽然这个还不足以令动态规划)useful in an efficient way(得到有效利用),but it at least tells you that you should(但至少告诉你你该干什么)..you should be able to try to apply it(你们应该能试着用上它).That's a pretty weak statement, but(这虽然是个很弱的命题 但是)it's something that you should check(也是你们要注意的一点).It's definitely pretty much a necessary condition for(这对于动态规划的有效性而言)dynamic programming to make sense(绝对是一个必要条件).And so, optimal some-structure here means that(那么 最优结构表示的是)if I take some shortest path(当我选定一条最短路径时),and I look at a subpath of that shortest path(我再观察这条最短路径的子路径),I claimed that it too is a shortest path(我肯定它也是一条最短路径).OK, with its respective endpoints(子路径对应的两个端点);obviously not between the same endpoints(显然不都是原路径的两端点).But if I have some shortest path between two endpoints(但如果两端点间 有一条最短路径的话),I take any subpath and that's also the shortest path(我取得任意一条子路径 都是最短子路径).This is one version of optimal substructure(这个最优子结构的一个版本).This one turns out to be true for this setup(这对于这里的前提条件是成立的).And, how should I prove an optimal substructure property(那么 我们该怎么证明一个最优子结构的性质)?Cut and paste(剪贴法).Yep, that works here too(在这里也用得上).I mean, this isn't always true(我的意思是 它不是总是有用).But it's a good technique here(但这里它是一个好方法).So, we're going to think about(好 让我们想想看)and I'll do essentially a proof by picture here(然后我准备画幅图来证明).So, suppose you have some subpath of some shortest path(好的 假如你有一些最短路径的子路径).So, let's say the subpath is x to y(我们设子路径从x到y).And, the path goes from u to v(最优路径是从u到v的).So, we assume that (u,v) is a shortest path(所以我们假设(u,v)是最短路径).We want to prove that(x,y) is a shortest path(我们要证明(x,y)也是最短路径).Well, suppose (x,y) isn't a shortest path(好的 假设(x,y)不是最短路径).Then there is some shorter path that goes from x to y(那么x到y之间就有一条更短的路径).But, if you have some shorter path from x to y than this one(但如果你在x到y之间有一条更短的路径).Then I should just erase this part(那么我只要把这一部分子路径)of the shortest path from u to v(从u到v的最短路径种擦掉),and replace it with this shorter one(然后将它替换为更短的路径). OK, so that's a good sign for computing shortest paths(看来求出最短路径 已经指日可待了).I mean, in terms of dynamic programming(我的意思是 就动态规划而言),we won't look directly at dynamic programming here because(我们不会直接对动态规划展开攻略), we are going to aim for greedy(因为我们要采用贪心策略 它更为强大),But, next Monday we'll see some dynamic programming approaches(但在下周一 我们会看到动态规划的方法).Intuitively, there are some pretty natural sub problems here(直观上看 这里很自然地会有一些子问题).I mean, going from u to v(从u到v).Maybe it involves computing shortest paths(它可能包括了)from u to some intermediate point, x(求从u到某个中间点x的最短路径),and then from x to u, something like that(然后再从x到u的最短路径 诸如此类).But thinking about this intermediate point(但是现在想一下中间点)we get something called the triangle inequality(我们知道有三角形不等式).It holds in all sorts of geometric spaces(它在所有的几何空间内都是成立的),but it also holds for shortest paths(对最短路径来说也是成立的),the shortest path from u to v is, at most(从u到v的最短路径 最大不超过),the shortest path from u to x plus(u到x的最短路径加上)the shortest path from x to v(x到v的最短路径).So, this should be pretty natural just from the statement(这个命题看起来相当顺理成章),even more natural if you draw the picture(画个图出来的话 更加好理解).So, we have some vertex, u(我们有个点u).I'm using wiggly lines to denote potentially long paths(我用曲线来表示那些可能更长的路径)as opposed to edges(与边相对).We have some intermediate point, x(我们有个中间点x),and we have some target, v(还有个目的点v),and we are considering these three shortest paths(然后我们考虑这三条最短路径).This is the shortest path from u to v(这条是从u到v的最短路径). In particular, which is always more exciting(而且会是 相当意思的算法).Today, we're going to look at a particular version of shortest paths(今天 我们准备看看最短路径的一个特殊的版本)called the single source shortest path problem(叫做单源最短路径问题).OK, it's a little bit more general than go from A to B(它比从A到B的定义要更广泛些).The problem is, you're given a source vertex(问题是 给你一个顶点作为源点),and how to get from that source vertex to everywhere else(怎么从源顶点到达所有的点).So, we'll call this source vertex s(好的 我们叫这个为源点S).And from that source, we want to find(从源点出发 我们想找出),let's say, the shortest path weights from s to everyone(从源点s 到其他所有点的最短距离).In particular,we'd also like to know the shortest paths(尤其是 我们想知道最短路径是什么).So, that's delta of s, v for all vertices, v(那么 这是对于所有v求delta(s,v)).The best algorithms for solving the A to B problem--------(解决A到B最短路径问题的最佳算法)given s, given t, go from s to t(已知s和t 从s到t),is no easier than this problem(不会比这个问题简单).Today, we're going to look at a further restriction on this problem(今天 我们要给这个问题加一些限制条件).But, today we're going to get rid of the negative weight cycle issue(负权值环的问题)by forbidding negative weights(所以禁止负权值的存在).So, we're going to assume that(所以 我们先假设).So, for all vertices, u and v(对于所有的u和v).So, in particular(也就是说),shortest paths exist, provided paths exist(最短路径存在 只要路径存在).And, we don't have to worry about these minus infinities(那么我们就不用担心负无穷的情况).It still might be plus infinity if there is no path(虽然没有路径的话 还会有正无穷的情况),but this will make life a lot easier(但至少能给我们省点脑细胞).And the algorithm we'll cover today really requires this property(我们今天讲的这个算法真的很依赖这个条件).You can't get away without it(没它不行).Next class, we'll get away without it(下节课 我们就可以去掉这个条件)with a fancier and slower algorithm(用一个酷炫但较慢的算法). So, as I hinted at(之前剧透过了),the main idea we're going to use for the algorithm today is greedy(我们今天的算法思想是 贪心),which should be faster than dynamic programming generally(它一般比动态规划要快).And, the tricky part will be(但有技巧的部分是)proving that the greedy algorithm actually works(如何证明贪心算法确实有效).So, let me give you a little bit of setup(我先给你们一些前提条件).The invariant we are going to maintain( 我们要维持一个不变量)is that at all times, we have(在任意时刻 我们都要)estimates on the distances from the source to every vertex(估算从源点到每个点的距离)When I say distance, I mean shortest path weight(我所说的距离 指的是最短路径的权值).I'm going to use weight and distance inlerchangeably here(我说的权值和距离可以互换的)And, in particular, I want to maintain the set of vertices(而且 我还想要维持那些)where those estimates are actually the right answer(估算距离已经是最短距离的顶点).OK, this is little s. This is big S.(这个是小写s 这个是大写S), the big S will be the set of all vertices where I know the answer(大写S是所有已知最短路径的顶点的集合).What is the shortest path distance(小写s到大写S集合中每个点)from little s to that vertex in big S(最短距离分别是多少)?So, for starters, which distance do I know(一开始时 我们知道的是哪些距离)?I know the shortest path distance from s to s(我知道的是s到S的最短距离)because if I assume that all of my weights are nonnegative(因为前提是所有边的权值都是非负的),I really can't get from s to S any faster than not doing anything(啥都不做总要比有任何动作都要快吧).OK, if I had a negative weight cycle, maybe(好吧 如果有负环的话 可能不一样)the distance from s to S is minus infinity(s到S的距离等于负无穷).So there's no way I can get from s to S any faster than zero time(所以这里我没法比0).There might be a longer path that still has zero cost(可能有条路绕多几个点 但费用还是0),but it can't be any better than zero(不过没有比0更快的了).So, in particular, I know that(所以 我知道).So, initially, s is certainly an S(一开始S里面肯定有一个s).So, at some point we know the distances from some of the vertices(某种程度上 我们知道到某些点的距离).This is S, and this is everything else(这是S 然后这是其它的东西).This is the graph, G(这个就是图G).This is the subset of the vertices(这个是顶点的子集合).And, there's some edges that go out from there(然后这些是从集合S里连出来的边).And, so we have estimates on how to get to these vertices(我们有 到外面一些点的距离估算).Some of them, we may not have even seen yet(但其中一些点 我们可能无法得知).They may not be connected to this portion of S(它们可能没有跟S里的点相连).They might be connected by some longer path(可能要通过更长的路才能相连).They might be in a completely different connected component(它们可能处于完全不同的连通分量里). Some of them, we have estimates for(我们已经估算出它们其中一部分)because we've sort of seen how to get there from S(因为我们已经知道怎么从连到那儿了).And the idea is, among all of these nodes where we have estimates(在这些已经估算好的点之中)and on to get from little S(然后从小写s出发的),which is some vertex in here, to these vertices(也就是里面的某个点 到外面的这些点),we're going to take the one for which the estimate is smallest(我们准备取它们中距离最小的那个).That's the greedy choice(这就是贪心的策略).And, we're just going to add that vertex to S(然后 我们就把那一点加入到S中).So, S grows one vertex per step(那么 S每一步都增加一个点).Each step, we're going to add to S, the vertex(每一步 我们加到S的点).Of course, again, this is not a unique(当然 可能不止一个点), it's a vertex, v, in V minus S(它是一个点v 在V减S的集合中).So, it's something we haven't yet computed yet(所以 这是一个还没经过验算的...)whose estimated distance from S is minimum(离S的距离最短的点).So, we look at all the vertices we haven't yet added to S(所以 我们观察所有还没加进S的点).Just take the one where we have the estimated smallest distance(然后从中选出距离最小的一个点).The intuition is that that should be a good choice(直觉告诉我 这是一个好的选择).So, if I pick the one that's closest to little s(如果我选的这一个离小s最近)among all the ones that I've seen(在所有我看到的顶点之中),I sort of have to buinin that those are good paths(我会认为这样能选出好的路径). But, I mean, maybe there's some path I didn't see(但是 我想说 可能还有些我们没看到的路径).Maybe you go out to here(或者当你走到这儿)and then you take some other path to some vertex(然后你另选一条新路径),which we've already seen(去一个曾经看过的点).I'd better not say that that's the shortest path(这个可能并不是最短路径)because there may have been some other way to get there(因为可能有别的路径能到那儿去).Right, as soon as I add something to S, I declare(好的 当我往S里加入某个点 我就说)I've solved the problem for that vertex(关于这个点的问题已经解决了).I can't change my answer later(我后面不会再改动它了).OK, the estimates can change until they get added to S(在被加入到S之前 估算距离可能会变).So, I don't want to add this vertex to S(所以 我不想把这个店加到S中)because I haven't considered this path(因为我还没考虑过这条路径).Well, if all my weights are nonnegative(那么 如果权值是非负的话),and I take the vertex here that has the shortest estimate from S(然后 我选取离S估算距离最短的点),so let's suppose this one is the shortest one(让我们假设这个是最短路径),then this can't be a shortest path(那这条路就不可能比它更短)because the distance estimate, at least, from S to that vertex(因为S到这个顶点的估算距离 至少)is larger from S to that vertex(要比S到那个点的大).So, no way can I make the path longer and decrease the distance(所以 不可能路绕远了 距离反而短了).But that's the intuition why this is the right thing to do(但这个推断说明这个方法是行的).You have to prove something about the distance estimates for that(你还需要对估算距离证明一些东西)to be proof(来证明).It was a good starting point(至少这个开局还挺顺的).And then presumably we have to maintain these distance estimates(可想而知 我们需要维护这些估算的距离).So, the heart of the algorithm is updating distance estimates(这个算法的核心就是更新估算距离).I mean, choosing the best vertex to add to S, that's one step(我是说 选出最好的点加入到S中 这是第一步).Then, updating the distance estimates is(然后 更新估算距离)sort of where the work is(这是最主要的一步).And, it turns out(事实上)we'll only need to update distance estimates of some of the vertices(我们只需要更新某些点的估算距离),the ones that are adjacent to v(就那些与v相连的点).v was the vertex we just added to S(v是指 刚刚加进S中的顶点).So, once we add somebody to S(一旦我们往S里加入某些点),so we grow S by a little bit(S就扩大了一点点),then we look at all the new edges that go out of S(然后我们观察最新连入S的那些边).From that vertex, we update something(那个顶点连什么 我们就更新什么).So, that's the idea for how we're going to use greedy(这就是怎么运用贪心策略的思路). So, this is called Dijkstra's algorithm(它的名字叫Dijkstra算法).So, the beginning of the algorithm is just some initializaion(这个算法一开始只是初始化),not too exciting(没什么特别).Ok, but let me tell you what some of the variables mean(好的 我先来告诉你们这些变量代表什么).OK, so d is some array indexed by vertices(好的 d是一个一顶点为下标的数组),and the idea is that d of x is the distance estimate for x(而d[x]则是起点到x的距离的估算距离),so, from S to x. So in particular(也就是从s到x 而且),it's going to equal the real shortest path weight from S to x(它将会是从s到x的真正的最短路径权值)when we've added x to our set capital, S(仅当我们把x加入到大写S集合中时).It's going to be the output to the algorithm(这就是这个算法的输出结果).So, in d of x, when we are done, d of x is the output(所以 当我们完成时 d[x]就是输出).For every vertex, it's going to give us(对于每个顶点 它最后都会给出)the shortest path weight from S to that vertex(从S到那个顶点的最短路径的权重).Along the way, it's going to be some estimated distance from S to that vertex(它都是从S到某一点的估算距离).And, we're going to improve it over time(然后 我们每次都更新它).This is an infinity(这个等于正无穷).So initially, we know that the distance(一开始时).So initially, we know that the distance from s to s is zero(点s到点s的距离为0).So, we're going to set that to be our estimate(我们把它作为估算距离).Everything else we're going to just set to infinity(其它的点 我们只需要设为正无穷)because we may not be connected(因为它们跟s可能不相连).S, initially, is going to be infinity(S一开始是正无穷).Immediately, we're going to add little s to big S(马上 我们就往S里加入小写s).And then, the interesting part here is Q(然后 最有趣的是这里有个Q),which is going to consist of (Q将会包括有),initially all the vertices in the graph(一开始是图中所有的点).And, it's going to not just be a queue as the letter suggests(这个Q不单说明了它是队列Queue).It's going to be a priority queue(它还是一个优先队列).So, it's going to maintain, in particular(特别地 它还要维护),the vertex that has the smallest distance estimate(有着最小估算距离的顶点).The vertices are keyed on d, our distance estimate(这些顶点以d为键).So, this is initialization(好的 这就是初始化). The heart of the algorithm is all in six lines(这个算法的核心全在这六行里).The first step here that we need to do is(我们要做的第一步是)we take the vertex whose distance estimate is minimum(我们取出估算距离最小的顶点).So that, among all the vertices, not yet(所以 在所有顶点中...),and that's currently S is empty, Q has everyone(当前的S为空集 Q有所有顶点).In general, Q will have everyone except S(一般来说 Q有除S外的所有顶点).So, we'll take the vertex, u(那么 我们取顶点u),that has the minimum key in that priority queue(它对应优先队列里 键值最小的顶点).So, extract the Min from Q(所以 从Q中取出最小值).We're going to add a little u to S(我们把u加入S中).We add to S that vertex that has minimum distance estimate(我们往S里加入估算距离最小的顶点).