《数据结构的第八讲》PPT课件.ppt

1,引言,现实世界存在许多不同类型的模拟系统。 例如：交通流量就是其中一个实例。 顶点表示街道的十字路口，同时边表示街道本身。 加权边可以用来表示车速限制或者车道数量。 模型可以使用系统来确定最佳路线和可能遭受交通堵塞的街道。 例如：航空公司的飞行系统。 每一个飞机场就是一个顶点，而从一个顶点到另一个顶点的航线就是一条边。 加权的边可以表示从一个机场到另一个机场飞行的费用，或者表示从一个机场到另一个机场的大概距离，这取决于模拟的内容。,由图模拟真实世界系统,第八讲 图和图的算法,主要内容,8.1 图的定义 8.2 图的存储表示 8.3 图的第一个应用：拓扑排序 8.4 图的搜索 8.5 最小生成树 8.6 查找最短路径,8.1 图的定义,5,图的定义,图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中： V = vi | vi 某个数据对象 是顶点的有穷非空集合； E = (vi, vj) | vi, vj V 或 E = | vi, vj V ( vi , vj ) 依附于 vi 和 vj,vi 邻接到 vj ; vj 邻接自 vi ; 相关联于 vi and vj,子图 G G : V( G ) V( G ) ,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,17,图的定义,有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。,18,图的定义,如果存在从任意顶点到其他任意顶点的路径，就认为无向图是连通的（ connected） 在有向图中，这个条件被称为是强连通（ strongly connected） 如果有向图不是强连通的，但是又认为连通了，这就被称为弱连通（ weakly connected）,19,图的定义,完全图: 边数最大的图,每组顶点之间都有边,20,图的定义,生成树： 一个连通图的生成树是其极小连通子图。 在n个顶点的情形下，有n-1条边。 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。 在极小连通子图中增加一条边，则一定有环。 在极小连通子图中去掉一条边，则成为非连通图。,21,图的定义,有n个顶点，n-1条边的图必定是生成树吗？,对非连通图，则称由各个连通分量的生成 树的集合为此非连通图的生成森林。,主要内容,8.1 图的定义 8.2 图的存储表示 8.3 图的第一个应用：拓扑排序 8.4 图的搜索 8.5 最小生成树 8.6 查找最短路径,8.2 图的存储表示,24,邻接矩阵(Adjacency Matrix),在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。 设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edgenn， 定义：,25,邻接矩阵举例,分析1： 无向图的邻接矩阵是对称的； 分析2： 顶点i 的度第 i 行 (列) 中1 的个数； 特别： 完全图的邻接矩阵中，对角元素为0，其余全1。,26,邻接矩阵举例,注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第j列含义：以结点vj为头的弧(即入度边）。,27,邻接矩阵举例,分析1： 有向图的邻接矩阵可能是不对称的 分析2： 顶点的出度=第i行元素之和 顶点的入度=第i列元素之和 顶点的度=第i行元素之和+第i列元素之和,28,网络（带权图）的邻接矩阵,29,顶点的表示,要开始构造 Graph类的第一步是构造存储图内顶点的 Vertex类。 这个类与 LinkedList类和 BinarySearchTree类中的 Node类具有相同的功效。 Vertex类需要两个数据成员： 一个用来识别顶点数据 一个布尔型成员则用来跟踪顶点的“访问”,30,顶点的表示,这两种数据成员分别命名为 Label wasVisited 此类需要的唯一方法就是允许设置数据成员 label和 wasVisited的构造器方法。 在这个实现中将不使用默认的构造器，这是因为每次开始引用顶点对象时都会进行一次实例化操作。 顶点列表会存储在数组内，而且在 Graph类中会通过它们在数组内的位置对其进行引用。,31,边的表示,边描述了图的结构，所以关于图的真实信息是存储在边内的。 选择用来表示图中边的方法称为是邻接矩阵。 邻接矩阵是一个二维数组，数组内的元素表示了两个顶点之间是否存在边。 把顶点作为矩阵内行和列的标头罗列出来。 如果在两个顶点之间存在一条边，那么就把 1放在这个位置上。 如果边不存在，那么就赋值为 0。很显然这里也可以使用布尔型的数值。,32,图的构造,有了表示顶点和边的方法，接下来就准备构造图了。 首先，需要建立一个图中顶点的列表。 最后，需要添加连接顶点的边。,33,Graph类的初步定义,构造器方法重新构建了顶点数组和在常量 NUM-VERTICES中指定数值的邻接矩阵。 既然数组是基于零的，所以数据成员 numVerts存储着顶点列表内当前的数量以便于把列表初始设置为 0。 AddVertex方法会为顶点标签取走一个字符串参数，实例化一个新的 Vertex对象，并且把它添加到顶点数组内。 AddEdge方法则会取走两个整型值参数。这些整数表示顶点，并且说明在它们之间存在一条边。 showVertex方法会显示出指定顶点的标签。,34,邻接表 (Adjacency List),邻接表: 是图的一种链式存储结构。 边的结点结构 adjvex; / 该边所指向的顶点的位置 nextarc;/ 指向下一条边指针 info; / 该边相关信息的指针,35,邻接表 (Adjacency List),顶点的结点结构 data; / 顶点信息 firstarc; /指向第一条依附该顶点的边,36,无向图的邻接表,同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(边结点), 结点中有另一顶点的下标 dest 和指针 link。,37,有向图的邻接表和逆邻接表,邻接表 (出边表),逆邻接表 (入边表),38,网络 (带权图) 的邻接表,(出边表),(顶点表),39,邻接表存储法的特点,它其实是对邻接矩阵法的一种改进 分析1: 对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。 分析2: 在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。 若是稀疏图，则比邻接矩阵表示法合适。,40,邻接表度的计算,怎样计算无向图顶点的度？,TD(Vi)=单链表中链接的结点个数,怎样计算有向图顶点的出度？ 怎样计算有向图顶点的入度？ 怎样计算有向图顶点Vi的度：,OD(Vi)单链出边表中链接的结点数 I D( Vi ) 邻接点为Vi的边个数,TD(Vi) = OD( Vi ) + I D( Vi ),41,邻接表的优缺点,邻接表的缺点：,邻接表的优点：,空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,42,邻接表与邻接矩阵有什么异同之处,1. 联系： 邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。 2. 区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。 3. 用途： 邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)； 邻接表多用于稀疏图的存储（en2),主要内容,8.1 图的定义 8.2 图的存储表示 8.3 图的第一个应用：拓扑排序 8.4 图的搜索 8.5 最小生成树 8.6 查找最短路径,8.3 图的第一个应用：拓扑排序,45,活动网络 (Activity Network),计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。 例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。,用顶点表示活动的网络 (AOV网络),46,举例,C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8,课程代号 课程名称 先修课程,47,建图,学生课程学习工程图,C8,C3,C5,C4,C9,C6,C7,C1,C2,48,AOV网络,用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络 (Activity On Vertices)。 在AOV网络中不能出现有向回路, 即有向环。 如果出现了有向环，则意味着某项活动应以自己作为先决条件。 对给定的AOV网络，必须先判断它是否存在有向环。,49,拓扑排序,检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点 (代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。 这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中, 则该网络中必定不会出现有向环。,50,拓扑排序,如果AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 例如, 对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,51,拓扑排序的方法, 输入AOV网络。令 n 为顶点个数。 在AOV网络中选一个没有直接前驱的顶点, 并输出之; 从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上 、步, 直到 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或 图中还有未输出的顶点, 但已跳出处理循环。说明图中还剩下一些顶点, 它们都有直接前驱。这时网络中必存在有向环。,52,C0,C1,C2,C3,C4,C5,(a) 有向无环图,拓扑排序的过程,53,最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。,(h) 拓扑排序完成,拓扑排序的过程,54,AOV网络及其邻接表表示,55,拓扑排序算法,使用一个存放入度为零的顶点的链式栈, 供选择和输出无前驱的顶点。 拓扑排序算法可描述如下： 建立入度为零的顶点栈; 当入度为零的顶点栈不空时, 重复执行 从顶点栈中退出一个顶点, 并输出之; 从AOV网络中删去这个顶点和它发出的边, 边的终顶点入度减一; 如果边的终顶点入度减至0, 则该顶点进入度为零的顶点栈; 如果输出顶点个数少于AOV网络的顶点个数, 则报告网络中存在有向环。,56,拓扑排序算法,1.找到一个没有后继顶点的顶点。 2.把此顶点添加到顶点列表内。 3.从图中移除掉此顶点。 4.重复步骤 1直到把所有顶点从图中移除掉。 在实现的细节上存在挑战， 但这正是拓扑排序的关键所在。,57,拓扑排序算法的实现,拓扑排序需要两个方法。 一个方法用来确定顶点是否有后继顶点 另一方法则是把顶点从图中删除 下面先来看看确定没有后继顶点的方法。 在邻接矩阵中可以找到没有后继的顶点，这种顶点所在行对应的所有列都为零。 方法会用嵌套的 for循环来逐行检查每组列的内容。 如果在某列发现 1，就跳出内部循环，并对下一行进行检查。 如果找到一行对应的所有列都为零，那么返回这个行号。 如果两层循环结束且没有行号返回，那么返回-1，这表示不存在无后继的顶点。,58,拓扑排序算法的实现,接下来需要明白如何从图中移除顶点。 需要做的第一件事就是从顶点列表中移除掉该顶点。这是很容易的。 然后，就需要从邻接矩阵中移除掉相应的行和列，同时还要把移除行上面的行向下移动并且把移除列右侧的列向左移动，以此来填充移除顶点留下的行和列的空白。 为了实现这个操作，这里编写了名为 delVertex的方法，它包括两个助手方法 moveRow和 moveCol,59,拓扑排序算法的实现,需要一个TopSort方法来控制排序的过程。 TopSort方法循环遍历图内顶点，找到一个无后继的顶点就把它删除，然后再移动到下一个顶点上。每次删除顶点时，会把它的标签压进一个栈内。 栈是一种使用便利的数据结构，因为找到第一个顶点实际上就是图内的最后一个顶点（或者是最后中的一个）。 当 TopSort方法运行完成的时候，栈内的内容将包括压入栈底的最后一个顶点和在栈顶的图的第一个顶点。 这时只需要循环遍历栈来弹出每个元素进行显示就是图的正确拓扑顺序了。,主要内容,8.1 图的定义 8.2 图的存储表示 8.3 图的第一个应用：拓扑排序 8.4 图的搜索 8.5 最小生成树 8.6 查找最短路径,8.4 图的搜索,62,引言,图的搜索是在图上经常执行的一种操作，通过该操作确定从一个顶点能到达哪些顶点是。 例如：人们可能需要知道在地图上哪些路可以从一个城镇到达其他城镇，或者从一个机场到其他机场可以走哪条航线。 在图上执行这些操作都用到了查找算法。 图上可以执行两种基础查找： 深度优先（depth-first）搜索 广度优先（breadth-first）搜索,深度优先搜索,深度优先搜索的含义是沿着一条路径从开始顶点到达最后的顶点， 然后原路返回， 并且沿着下一条路径达到最后的顶点， 如此继续直到走过所有路径。,63,深度优先搜索算法的工作过程,首先，选取一个起始点，它可能是任何顶点。访问这个顶点，把它压入一个栈内，并且标记为已访问的。 接着转到下一个未访问的顶点，也把它压入栈内，并且做好标记。 继续这样的操作直到到达最后一个顶点为止。 然后，检查栈顶的顶点是否还有其他未访问的相邻顶点。 如果没有，就把它从栈内弹出，并且检查下一个顶点。 如果找到一个这样的顶点，那么就开始访问相邻顶点直到没有未访问的为止，还要检查更多未访问的相邻顶点并且继续此过程。 当最终到达栈内最后一个顶点并且没有相邻的未访问顶点的时候，才算完成深度优先搜索。,64,深度优先搜索,65,dfs ( 0 ),Tp = O( n + e )(邻接表) Tp = O( n2 ).(邻接矩阵),练习,66,对下列非连通图 G 进行深度优先搜索遍历，得到顶点的访问序列为：,计算机如何实现DFS,67,DFS 结果,邻接矩阵 A,辅助数组 visited n ,起点,v2v1v3v5v4v6,开辅助数组 visited n ！,例：,在图的邻接表中如何进行DFS,照样借用visited n ！,v0 v1 v2 v3,DFS 结果,辅助数组 visited n ,例：,起点,0 1 2 3,注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。,DFS 算法效率分析,69,（设图中有 n 个顶点，e 条边） 如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。 如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,结论： 稠密图适于在邻接矩阵上进行深度遍历； 稀疏图适于在邻接表上进行深度遍历。,广度优先搜索,广度优先搜索算法会从第一个顶点开始尝试访问所有可能在第一个顶点附近的顶点。 从本质上说，这种搜索在图上的移动是逐层进行的， 首先会检查与第一个顶点相邻的层， 然后逐步向下检查远离初始顶点的层。,70,广度优先搜索算法,1.找到一个与当前顶点相邻的未访问过的顶点，把它标记为已访问的，然后把它添加到队列中。 2.如果找不到一个未访问过的相邻顶点，那么从队列中移除掉一个顶点（只要队列中有顶点可以移除掉），把它作为当前顶点，然后重新开始。 3.如果由于队列为空而无法执行第二步操作，那么此算法就此结束。,71,广度优先搜索,72,bfs ( 0 ),Tp = O( n + e )(邻接表) Tp = O( n2 ).(邻接矩阵),计算机如何实现BFS,73,除辅助数组visited n 外，还需再开一辅助队列！,邻接表,例：,起点,辅助队列,v2已访问过了,BFS 遍历结果,入队！,初始f=n-1,r=0,BFS 算法效率分析,74,DFS与BFS之比较： 空间复杂度相同，都是O(n)(借用了堆栈或队列）； 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,如果使用邻接表来表示图，则BFS循环的总时间代价为 d0 + d1 + + dn-1 = O(e)，其中的 di 是顶点 i 的度。 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。,（设图中有 n 个顶点，e 条边）,练习,75,对下列连通图 G 进行广度优先搜索遍历，得到顶点的访问序列为：,主要内容,8.1 图的定义 8.2 图的存储表示 8.3 图的第一个应用：拓扑排序 8.4 图的搜索 8.5 最小生成树 8.6 查找最短路径,8.5 最小生成树,最小生成树,当设计网络的时候，网络节点之间的连接数量很可能会多于最小连接数量。额外的连接是一种资源浪费，应该尽可能地消除它。额外的连接也会使其他人对网络的研究和理解变得不必要的复杂。因此需要使得网络只包含对节点连接而言最小数量的必要连接。当把这种网络应用到图上的时候，这样的网络就被称为是最小生成树。 最小生成树的得名源于覆盖每个顶点（范围）所必需的最少数量的构造边，而且说它是树是因为结果图是非循环的。需要牢记一个重要的内容：一张图可能包含多个最小生成树。创建的最小生成树完全依赖于初始顶点。,78,最小生成树算法,79,画出下图的生成树,最小生成树,80,首先明确： 使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。,即有权图,目标： 在网络的多个生成树中，寻找一个各边权值之和最小的生成树。,构造最小生成树的准则 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用n-1条边来联结网络中的n个顶点； 不能使用产生回路的边。,典型用途,81,欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n1条线路，使总费用最少？,数学模型： 顶点表示城市，有n个； 边表示线路，有n1条； 边的权值表示线路的经济代价； 连通网表示n个城市间通信网。,显然此连通网是一个生成树！,问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(Minimum cost Spanning Tree),如何求得最小生成树,82,有多种算法，但最常用的是以下两种：,最小生成树的 MST 性质如下：,Kruskal（克鲁斯卡尔）算法 Prim（普里姆）算法,Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。 Prime算法特点: 将顶点归并，与边数无关，适于稠密网。 这两个算法，都是利用MST 性质来构造最小生成树的。,若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0, v0)必在最小生成树上。,克鲁斯卡尔（Kruskal）算法,83,步骤： (1) 首先构造一个只有 n 个顶点但没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。 (2) 当在边集 E 中选到一条具有最小权值的边时,若该边的两个顶点落在T中不同的连通分量上，则将此边加入到生成树的边集合T 中；否则将此边舍去，重新选择一条权值最小的边。 (3) 如此重复下去，直到所有顶点在同一个连通分量上为止。此时的T即为所求（最小生成树）。,设N = V, E 是有 n 个顶点的连通网，,Kruskal算法采用邻接表作为图的存储表示,Kruskal算法,84,例 ：,1、初始连通分量：1,2,3,4,5,6 2、反复执行添加、放弃动作。条件：边数不等于 n-1时 边 动作连通分量 (1,3) 添加1,3,4,5,6,2 (4,6) 添加1,3,4, 6,2,5 (2,5) 添加1,3,4, 6,2,5 (3,6) 添加1,3,4, 6,2,5 (1,4) 放弃因构成回路 (3,4) 放弃因构成回路 (2,3) 添加1,3,4,5,6,2,普里姆(Prim)算法,普里姆算法的基本思想： 从连通网络 N = V, E 中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合U中。 以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。 如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。 采用邻接矩阵作为图的存储表示。,85,Prim算法,86,例：,1,注：在最小生成树的生成过程中，所选的边都是 一端在V-U中，另一端在U中。,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图,12,操作演示,-1 28 10 ,lowcost,closeVertex,0 1 2 3 4 5 6,选 v=5,选边 (0,5),-1 28 25 -1 ,lowcost,closeVertex,0 1 2 3 4 5 6,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图,12,选 v=4,选边 (5,4),操作演示,-1 28 22 25 -1 24,lowcost,closeVertex,0 1 2 3 4 5 6,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图,12,选 v=3,选边 (4,3),操作演示,主要内容,8.1 图的定义 8.2 图的存储表示 8.3 图的第一个应用：拓扑排序 8.4 图的搜索 8.5 最小生成树 8.6 查找最短路径,8.6 查找最短路径,查找最短路径,最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 问题解法 边上权值非负情形的单源最短路径问题 Dijkstra算法 边上权值为任意值的单源最短路径问题 Bellman和Ford算法 所有顶点之间的最短路径 Floyd算法,92,权值非负情形的单源最短路径问题,问题的提法： 给定一个带权有向图D与源点 v，求从 v 到D中其它顶点的最短路径。限定各边上的权值大于或等于0。 为求得这些最短路径, Dijkstra提出按路径长度的递增次序, 逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。,93,举例说明,94,迭代 S u dis2 dis3 dis4 dis5 初始 1 - 10 30 100 1 1,2 2 10 60 30 100 2 1,2,4 4 10 50 30 90 3 1,2,4,3 3 10 50 30 60 4 1,2,4,3,5 5 10 50 30 60,1,2,5,4,3,10,20,50,100,30,10,60,赋权图G,由数组Di可知：从顶点1到顶点2、3、4、5的最短通路的长度分别为10、50、30和60。,Dijkstra算法, 初始化： S v0 ; distj Edge0j, j = 1, 2, , n-1; / n为图中顶点个数 求出最短路径的长度： distk min disti , i V- S ; S S U k ; 修改： disti min disti, distk + Edgeki , 对于每一个 i V- S ; 判断：若 S = V, 则算法结束，否则转 。,95,