Chapter13-贪婪算法-2

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,LOGO,Chapter13,贪婪算法,2024/9/13,1,内容提要,13.1,示例问题提出,13.2,贪婪算法的思想,13.3,贪婪算法的应用,货箱装船,拓扑排序,单源最短路径,最小耗费生成树,2024/9/13,2,贪婪算法应用,拓扑排序,单源点最短路径,Dijkstra,算法,最小耗费生成树,Kruskal,算法,Prime,算法,Sollin,算法,2024/9/13,3,1,、拓扑排序,DAG,图：有向无环图,几乎所有的工程（,project,）都可分为若干个称作,“,活动,”,的子工程，并且这些子工程之间通常受着一定条件的约束，例如其中某些子工程必须在另一些子工程完成之后才能开始,对整个工程和系统，主要关心两方面的问题：,工程能否顺利进行,拓扑排序,；,完成整个工程所必须的最短时间,求关键路径,2024/9/13,4,顶点表示活动的网络,(Activity On Vertices:,AOV,网络,),用有向图表示一个工程。在这种有向图中，,用,顶点表示活动,，,有向边,表示活动,V,i,必须先于活动,V,j,进行。,顶点表示活动的网络,(Activity On Vertices),，,AOV,网络。,在,AOV,网络中，如果活动,V,i,必须在活动,V,j,之前进行，则存在有向边,，,AOV,网络中不能出现有向回路，即有向环。,在,AOV,网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。,对给定的,AOV,网络，,必须先判断它是否存在有向环,。,2024/9/13,5,AOV,网络示例：选课问题,课程,代号 课程名称 先修课程,C,1,高等数学,C,2,程序设计基础,C,3,离散数学,C,1, C,2,C,4,数据结构,C,3, C,2,C,5,高级语言程序设计,C,2,C,6,编译方法,C,5, C,4,C,7,操作系统,C,4, C,9,C,8,普通物理,C,1,C,9,计算机原理,C,8,2024/9/13,6,C1,C4,C3,C7,C9,C8,C2,C5,C6,表示课程之间优先关系的有向图,2024/9/13,7,检测有向环的方法,拓扑排序,检测有向环的一种方法是对,AOV,网络构造它的拓扑有序序列。,即将各个顶点 （代表各个活动）排列成一个线性有序的序列，使得,AOV,网络中所有应存在的前驱和后继关系都能得到满足。,这种构造,AOV,网络全部顶点的拓扑有序序列的运算就叫做,拓扑排序,。,如果通过拓扑排序能将,AOV,网络的所有顶点都排入一个拓扑有序的序列中，则该,AOV,网络中必定不会出现有向环；反之，说明,AOV,网络存在有向环，工程不可行。,2024/9/13,8,拓扑排序方法,（,1,）输入,AOV,网络。令,n,为顶点个数。,（,2,）在,AOV,网络中选一个,没有直接前驱的顶点,， 并输出之；,重复以上（,2,）、（,3,）步,直到,（,3,）从图中删去该顶点， 同时,删去所有它发出的有向边,；,全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环,这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时,AOV,网络中必定存在有向环。,2024/9/13,9,C,0,C,3,C,1,C,5,C,2,C,4,C,0,C,3,C,1,C,5,C,2,C,4,C,0,C,3,C,1,C,5,C,2,C,3,C,1,C,5,C,2,拓扑排序的过程,2024/9/13,10,最后得到的拓扑有序序列为,C,4, C,0, C,3, C,2, C,1, C,5,。满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶,点，如,C,4,和,C,2,，,也排出了先后次序关系。,C,1,C,5,C,2,C,1,C,5,C,5,拓扑排序的过程（续）,2024/9/13,11,课堂练习：学生选课的拓扑序列,C1,C4,C3,C7,C9,C8,C2,C5,C6,2024/9/13,12,拓扑排序用贪婪算法实现,设,n,是有向图中的顶点数,设,V,是一个空序列,while(true,),设,w,不存在入边（,v,w,），其中顶点,v,不在,V,中,如果没有这样的,w,，,break,。,把,w,添加到,V,的尾部,if(V,中的顶点个数少于,n),算法失败,else V,是一个拓扑序列,2024/9/13,13,数据结构的选择,输出序列,V,：用一维数组来描述,;,用一个栈来保存加入,V,的候选顶点；,另有一个一维数组,InDegree,，,InDegreej,表示与顶点,j,相连的节点,i,的数目，其中顶点,i,不是,V,中的成员，它们之间的有向图的边表示为（,i,，,j,）。,2024/9/13,14,bool,Network:Topological(int,v) ,int,n = Vertices();,int,*,InDegree,= new,int,n+1;,InitializePos,();,for (,int,i = 1; i = n; i+),InDegreei, = 0;,for (i = 1; i = n; i+),首先计算每个顶点的入度,int,u =,Begin(i,);,while (u),InDegreeu,+;,u =,NextVertex(i,);,邻接矩阵：,(n,2,),邻接链表：,(,n+e,),2024/9/13,15,LinkedStack, S;,for (i = 1; i ,d,i, +,a,i,j,）,经过已经求得最短路径的顶点到达终点,即,d,j, = min,d,j,d,i, +,a,i,j, ,else,不修改,源点直接到达终点,d,j,与,d,i, +,a,i,j,的大小,2024/9/13,28,L,表,源点未到达顶点表,采用数据结构：无序链表,VS.,最小堆,初始值：与源点邻接的顶点链表,更新情况：某个顶点,j,的,dj,发生变化，且不在,L,中，则加入到链表中,2024/9/13,29,Dijkstar,算法伪代码,（,1,）初始化,di,=,asi,（,1in),对于邻接于,s,的所有顶点,i,，置,pi,=s,，对于其余的顶点,pi,=0;,对于,pi, 0,的所有顶点建立,L,表；,（,2,）若,L,为空，终止，否则转至（,3,）,（,3,）从,L,中删除,d,值最小的顶点，标识为,i,；,（,4,）对于与,i,邻接的所有还未到达的顶点,j,，更新,dj,值为,mindj,di+aij,；若,dj,发生了变化且,j,还未在,L,中，则置,pj,=i,，并将,j,加入,L,，转至（,2,）。,2024/9/13,30,例,终点,从顶点,1,到各终点的,di,值和最短路径,1,2,4,4,4,3,2,4,3,5,8,8,6,6,i,3,4,2,5,S=1,1,3,1,3,4,1,3,4,2,1,3,4,2,5,a,=,4,2,8,4,5,1,3,1,3,1,3,4,1,2,1,3,4,5,2024/9/13,31,Dijkstar,算法（程序,13-5,）,template,void,AdjacencyWDigraph,:,ShortestPaths(int,s,T,d,int,p), if (s n) throw,OutOfBounds,( );,Chain L;,/,未到达顶点链表,ChainIterator, I;,/,链表遍历器,/ initialize d, p, and L,for (,int,i = 1; i = n; i+),di, =,asi,;,if (,di, =,NoEdge,),pi, = 0;,else ,pi, = s; L.Insert(0,i); ,2024/9/13,32,a,=,4,2,8,4,5,1,3,i,1,2,3,4,5,di,4,2,8,pi,0,1,1,0,1,初始化,d,，,p,5,3,2,NULL,初始化,L,i=3,2024/9/13,33,/ L,表为空，表示所有顶点均找到路径,while (!,L.IsEmpty,( ),/,在未到达顶点,L,表中，查找,d,值最小的顶点,int,*v =,I.Initialize(L,);,int,*w =,I.Next,( );,while (w),if (d*w d*v) v = w;,w =,I.Next,( );,Dijkstar,算法（程序,13-5,）,2024/9/13,34,/,顶点,*v,作为下一个源点，搜索与之关联的顶点,j,/,若顶点,j,的,d,值不是最优，则更新,dj,和,pj,int,i = *v;,L.Delete,(*v);,for (,int,j = 1; j ,di, +,aij,),dj, =,di, +,aij,;,更新,dj,为最优值,if (!,pj,) L.Insert(0,j);,pj, = i;,更新其前驱顶点, / End of while (!,L.IsEmpty,( ),Dijkstar,算法（程序,13-5,）,2024/9/13,35,终点,从顶点,1,到各终点的,di,值和最短路径,2,4,4,4,3,2,4,3,5,8,8,6,6,i,3,4,2,5,S=1,1,3,1,3,4,1,3,4,2,1,3,4,2,5,L,链表的变化,d,的变化,L,的变化,p,的变化,初始值：,5-3-2 0 1 1 0 1,Step1,：,i=3, 5-2,，,d4=3 4-5-2 p4=3,Step2,：,i=4, 5-2, d5=6 p5=4,Step3,：,i=2, 5,Step4,：,i=5,空,0 1 1 3 4,反向输出,P,2024/9/13,36,对于具有,n,个顶点和,e,条边的带权有向图，,无论采用邻接矩阵，还是邻接链表，时间复杂度均为,O(n,2,),原因：必须至少对每一条边检查一次！,邻接矩阵仅能优化最后一个循环,O(e,),Dijkstar,算法复杂度分析,2024/9/13,37,【,问题描述,】,已知一个各边权值均大于,0,的带权有向图，对每一对顶点,v,i,v,j,，要求求出,v,i,与,v,j,之间的最短路径和最短路径长度。,【,解决方法一,】,：轮流以每一个顶点为源点，重复执行,Dijkstra,算法,n,次，即可求得每一对顶点之间的最短路径，总的时间复杂度为,O(n,3,),。,【,思考,】,如何求所有顶点之间的最短路径,【,解决方法二,】,：,Floyd（弗洛伊德）算法,2024/9/13,38,【,生成树定义,】,已知,G(V,E),是一个无向连通图，,E(G),为图,G,的边集，则从图中任一顶点出发遍历图时，必定将,E(G),分成两个集合,T(G),和,B(G):,T(G),：遍历图,G,时,所经过的边,的集合；,B(G),：遍历图,G,时,未经过的边,的集合；,则,G=(V,T),称为,G,的一棵生成树。,3,、最小生成树,2024/9/13,39,（,1,）,G,是图,G,的,极小连通子图,，即,G,中有,n,个顶点，,n-1,条边；,（,2,）无向连通图的生成树不是唯一的，对连通图不同的遍历，就得到不同的生成树。,1,3,2,6,5,4,1,3,2,6,5,4,1,3,2,6,5,4,例,深度优先生成树,广度优先生成树,生成树的特点,2024/9/13,40,（,1,）深度优先生成树：由深度优先搜索得到的；,（,2,）广度优先生成树：由广度优先搜索得到的。,对于一个,带权的连通图,，如何找出一棵生成树，使得各边上的,权值总和达到最小,，是一个有实际意义的问题。,生成树的类型,2024/9/13,41,【,构造原则,】,（,2,）尽可能选取权值小的边，但,不能构成回路（环）,；,（,3,）必须使用且仅使用,n-1,条边,，使,n,个顶点连通起来。,（,1,）必须只使用该网络中的边来构造；,给定一个无向连通网,G,，在,G,的所有生成树中，某一棵生成树其,n-1,条,边上权值之和为最小,，则这棵生成树为最小生成树。,WG(T,min,)=,minWG(T)|T,ST,最小耗费（代价）生成树及构造原则,2024/9/13,42,最小耗费生成树构造方法,三种方法：,Kruskal,方法：克鲁斯卡尔,Prim,方法：普里姆,Sollin,方法,2024/9/13,43,选择,n-1,条边；,【,贪婪准则,】,从剩下的边中选择一条,不会产生环路,的,具有最小耗费,的边加入已选择的边的集合中。,（,1,）,Kruskal,算法,【,注意,】,加入边不能产生环路，否则得不到生成树 。,是一种按照网中,边的权值递增,的顺序构造最小生成树的方法。,2024/9/13,44,按权值递增的次序选择,n-1,条边，每选一条边，要判断是否构成回路。,（,1,）设无向图连通网为,G(V,E),，,T,为,G,的最小生成树，初始时,T=V,（此时,T,中有,n,个连通分量）；,（,2,）,按照边的权值递增的顺序,，考察,E(G),中的每条边,e,，判断加入,e,后，,T,中的边是否构成回路；,（,3,）依次判断,E(G),中的每条边，直到,T,的连通分量为,1,时（或,T,的边数为,n-1,时），此连通分量,T,即为,G,的一棵最小生成树。,Kruskal,算法思想,2024/9/13,45,1,3,6,2,4,5,16,10,21,11,6,6,5,14,33,18,6,1,3,2,4,5,5,6,10,11,16,G,T,V(G)=1,2,3,4,5,6,E(G)= (1,2),(1,5),(1,6),(2,3), (2,4),(2,6),(3,4),(4,5),(4,6),(5,6),V(T)=1,2,3,4,5,6,E(T)= (2,3),(3,4),(1,5), (2,6),(1,2) ,Kruskal,算法示例,2024/9/13,46,（,1,）,V(T),V(G),，置,E(T),的初态为空集；,（,2,）,while,（,E(T),中的边数,n,）,从,E(G),中选取权值最小的边,e,，并从,E(G),中删去它；,if,（边,e,加入,E(T),中不构成回路）,将边,e,加入,E(T),中；,边数加,1,；,Kruskal,算法伪码描述,2024/9/13,47,初始用最小堆存放,E,中所有的边，构造过程中存放剩余的边；,用并查集的运算，检查依附于一条边的两个顶点是否同在一个连通分量上（即是否同在并查集的一个子集合上）,是，则舍去这条边；,否，将此边加入最小生成树,T,中，并将这两个顶点放在同一个连通分量上；,直到形成一个连通分量为止。,利用最小堆和,并查集,实现,Kruskal,算法,2024/9/13,48,补充：集合的树形表示方法,假设集合,S,由若干个元素组成，可以按照某一规则把集合,S,分成若干个互不相交的子集合，称之为,等价分类,。,例如，集合,S=1,2,3,4,5,6,7,8,9,10,，可以分成如下三个不相交的子集合：,S1=1,2,4,7,S2=3,5,8,S3=6,9,10,同样，也可以将两个集合合并成一个新的集合：,S1S2=1,，,2,，,3,，,4,，,5,，,7,，,8,P268 8.10.2,在线等价类,2024/9/13,49,用一棵树表示一个集合，树中的一个结点表示集合,中的一个元素，树结构采用,双亲表示法,。,1,7,4,2,3,8,5,6,10,9,S1=1,2,4,7,S2=3,5,8,S3=6,9,10,求集合的并集：把一个集合的树根结点作为另一个集合的树根结点的孩子结点。,查找某个元素所在的集合，可以沿着该元素的双亲域向上查，当查到某个元素的双亲域值为,0,时，该元素就是所查元素所属的树根结点。,2024/9/13,50,并查集支持以下三种操作：,Union (Root1, Root2) /,并操作，把子集合,Root2,并入,Root1,Find (x) /,搜索单元素,x,所在的集合，并返回该集合的名字,UnionFind,(s) /,构造函数，将并查集中,s,个元素初始化为只有一个单元素的子集合。,对于并查集来说，每个集合用一棵树表示。集合元素的编号从,1,到,n,。其中,n,是最大元素个数,并查集,(Union-Find Sets),1,3,6,2,4,5,16,10,21,11,6,6,5,14,33,18,2024/9/13,51,class,UnionFind,public:,UnionFind(int,Size = 10);,UnionFind,(), delete parent; delete root; ,void,Union(int,int,);,int,Find(int,);,private:,int,*parent;,保存该树中节点的个数,bool,*root;,根节点标志,;,并查集类的定义,2024/9/13,52,UnionFind:UnionFind(int,n),/,初始化，一个元素作为一类或一棵树,root = new booln+1;,parent = new intn+1;,for (,int,e = 1; e = n; e+),parente, = 1;,节点个数为,1,roote, = true;,为根节点,并查集类的初始化,2024/9/13,53,void,UnionFind:Union(int,i,int,j),if (,parenti, ,parentj,),将,i,作为,j,的子树,parentj, +=,parenti,;,rooti, = false;,parenti, = j;,else,将,j,作为,i,的子树,parenti, +=,parentj,;,rootj, = false;,parentj, = i;,并查集类：合并算法,重量规则,P271,1,7,4,2,3,8,5,1,7,4,2,3,8,5,2024/9/13,54,int,UnionFind:Find(int,e),int,j = e;,while (!,rootj,) j =,parentj,;,找到包含,e,的树的根,int,f = e;,while (f != j),int,pf =,parentf,;,parentf, = j;,f = pf;,return j;,并查集类：查找算法,路径压缩,P273,一旦查找成功，修改从查找节点到根的,路径上所有节点的指针，直接指向根节点,2024/9/13,55,边节点定义,template ,class,EdgeNode,friend,ostream,& operator(,ostream,&,EdgeNode,);,friend,UNetwork,;,friend void,main(void,);,public:,operator T () const return weight; ,private:,T weight;,/,边上权值,int,u, v;,/,边的起点、终点号,;,template,ostream,& operator(,ostream,& out,EdgeNode, x), out ,x.u, ,x.v, ,x.weight,; return out; ,2024/9/13,56,遍历器定义,13-7:,注意派生体系,LinkedWGraph,LinkedWDiGraph,LinkedBase,Network,WNetwork,UNetwork,virtual,定义遍历器,实现遍历器,Kruskal,实现,使用入口,2024/9/13,57,Kruskal,算法（程序,13-6,）,template,t0.n-2,中返回最小生成树,bool,UNetwork,:,Kruskal(EdgeNode, t ),int,n = Vertices( );,int,e = Edges( );,/,建立网络边节点数组,InitializePos,( );,EdgeNode, *E = new,EdgeNode, e+1;,int,k = 0; / cursor for E,2024/9/13,58,for (,int,i = 1; i = n; i+),int,j;,T c;,First(i, j, c);,while (j),if (i j),E+k.weight,= c;,Ek.u,= i;,Ek.v,= j;,Next(i, j, c);,/,使用最小堆初始化边节点数组,MinHeap, H(1);,H.Initialize(E, e, e);,按照顶点编号，依次找到与该顶点邻接的边，并记录到边节点数组中，形如,(i, j, c),2024/9/13,59,UnionFind,U(n,);,k = 0;,while (e & k n - 1),/n-1,条边,EdgeNode, x;,H.DeleteMin(x,);,/,最小耗费边,e-;,int,a =,U.Find(x.u,);,查找新加的边的两个顶点,int,b =,U.Find(x.v,);,属于同一个顶点集合！,if (a != b),tk,+ = x;,/,记录最小生成树的一个边节点,U.Union(a,b,);,DeactivatePos,();,H.Deactivate,();,return (k = n - 1);,时间复杂度,O(n+eloge,),2024/9/13,60,每次选择多条边来创建最小生成树，,选择下一条边的,【,贪婪准则,】,：从剩下的边中选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。,【,注意,】,可从任一顶点开始，往,T,中加入一条代价最小的边,(,u,v,),，使,T,与,(,u,v,),的并仍是一棵树。,（,2,）,Prim,算法,2024/9/13,61,已知连通网,G=(V,E),，设其最小生成树,G=(U,T),（,1,）初始时，令集合,U=u,0,（假设构造最小生成树时，从顶点,u,0,出发）；集合,T=,；,（,2,）从所有,u,U,，,v,V,-U,的边中，选取具有最小权值的边（,u,v,），将顶点,v,加入集合,U,中，将边,(,u,v,),加入集合,T,中；,（,3,）重复（,2,），直到,U=V,时，最小生成树构造完毕，集合,T,中包含了最小生成树的所有边。,Prim,算法思想,2024/9/13,62,6,1,3,2,4,5,1,3,6,2,4,5,16,10,21,11,6,6,5,14,33,18,5,10,11,16,6,Prim,算法构造最小生成树示例,U 1 ,，,V-U2, 3, 4, 5, 6,U 1,5 ,，,V-U2, 3, 4, 6,U 1,5,2,，,V-U3, 4, 6,U 1,5,2,3,，,V-U4, 6,U 1,5,2,3,4,，,V-U6,U 1,5,2,3,4,6,，,V-U,空,时间复杂度,O(n,2,),2024/9/13,63,Prim,算法伪代码,/,假设网络中至少具有一个顶点,设,T,为所选择的边的集合，初始化,T=,设,TV,为已在树中的顶点的集合，置,TV=1,令,E,为网络中边的集合,while,（,E!=,)&(|T|!=n-1),令,(,u,v,),为最小代价边，其中,uTV,，,v V-TV,if,（没有这种边）,break,E=E-(,u-v,) /,从,E,中删除此边,在,T,中加入边（,u,v,）,if(|T,|=n-1)T,是一棵最小生成树,else,网络是不连通的，没有最小生成树,2024/9/13,64,Kruskal,VS. Prim,Kruskal,算法的时间复杂度：,O(n+eloge,),Prim,算法的时间复杂度：,O(n,2,),结论：,Kruskal,算法与网中边数相关，适合求,边稀疏,的网的最小生成树,Prim,算法只与网中节点数相关，适合求,边稠密,的网的最小生成树,2024/9/13,65,（,3,）,Solin,算法：了解,算法每步选择若干条边，在每步开始时，所选择的边及图中的,n,个顶点形成一个生成树的森林，,选择边的,【,贪婪准则,】,：在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。,【,注意,】,一个森林中的两棵树可以选择同一条边，因此必须多次复制同一条边。,2024/9/13,66,贪婪算法总结,用于求解最优化问题,选择,可行性检查,解答检查,选择过程总是选择局部的最佳者,由空集合开始，循序加入新解来得到最后的答案,不保证一定会得到最佳解，需要证明,2024/9/13,67,贪婪算法的思想,贪婪算法的应用,拓扑排序,单源点最短路径,最小生成树,本章小结,2024/9/13,68,课后练习,Page432,：练习,27,提高篇：搜集资料，实现,Prim,算法,2024/9/13,69,实习五 贪婪算法应用,【,问题描述,】,设计一个校园导游程序，为来访的客人提供各种信息查询服务。,【,基本要求,】,（,1,）设计学校的校园平面图，所含景点不少于,10,个。图中顶点表示校内各景点，存放,景点名称、代号、简介,等信息；以边表示路径，存放路径长度等相关信息。,（,2,）为来访客人提供图中任意景点相关信息查询；,（,3,）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。,2024/9/13,70,【,测试数据,】,根据实际情况指定。,【,实现提示,】,一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网（,带权无向图,）。顶点和边均含有相关信息。,2024/9/13,71,弗洛伊德算法仍然使用前面定义的图的邻接矩阵,Edgenn,来存储带权有向图。,设置一个,nn,的矩阵,A,(k,),，其中除对角线的元素都等于,0,外，其它元素,a,(k),ij,表示顶点,v,i,到顶点,v,j,的路径长度，,k,表示运算步骤。,算法的基本思想,开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为,；,多源点最短路径算法,: Floyd,（弗洛伊德）,2024/9/13,72,以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：,第一步，让所有边上,加入中间顶点,v,0,，取,Aij,与,Ai0+A0j,中较小的值作,Aij,的值,，完成后得到,A,(1),，,第二步，让所有边上,加入中间顶点,v,1,，取,Aij,与,Ai1+A1j,中较小的值,，完成后得到,A,(2),，如此进行下去，当第,n,步完成后，得到,A,(n,),，,A,(n,),即为我们所求结果，,A,(n),ij,表示顶点,i,到顶点,j,的最短距离。,2024/9/13,73,A,(0),i,j,是从顶点,v,i,到,v,j,中间顶点是,v,0,的最短路径的长度,A,(,k,),i,j,是从顶点,v,i,到,v,j,中间顶点的序号不大于,k,的最短路径的长度，,A,(,n-,1),i,j,是从顶点,v,i,到,v,j,的最短路径长度。,定义一个,n,阶方阵序列：,A,(-1),A,(0), ,A,(,n-,1),.,其中,A,(-1),i,j, =,Edge,i,j,；,A,(,k,),i,j, = min ,A,(,k,-1),i,j,，,A,(,k,-1),i,k, +,A,(,k,-1),k,j, ,k,= 0,1,n,-1,Floyd,算法描述,2024/9/13,74,void,Graph,:,AllLengths,( const,int,n,),for (,int,i =,0;,i n,;,i,+ ),/,矩阵,a,与,path,初始化,for (,int,j =,0;,j n,;,j,+ ),a,i,j, =,Edge,i,j,;,if (,i,!=,j,&,a,i,j, INT_MAX ),path,i,j, =,i,;,/,i,到,j,有路径,else,path,i,j, = 0;,/,i,到,j,无路径,所有各对顶点之间的最短路径,为方便求出中间经过的路径，增设一个辅助二维数组,pathnn,，其中,pathij,是相应路径上顶点,j,的前一顶点的顶点号。,2024/9/13,75,for (,int,k,= 0;,k,n,;,k,+ ),/,产生,a,(,k,),及,path,(,k,),for (,i =,0;,i n,;,i,+ ),for (,j =,0;,j n,;,j,+ ),if (,a,i,k, +,a,k,j, ,a,i,j, ),a,i,j, =,a,i,k, +,a,k,j,;,path,i,j, =,path,k,j,;, /,缩短路径长度,绕过,k,到,j,算法的时间复杂度：,O(,n,3,),2024/9/13,76,2,3,0,1,3,2,1,4,5,9,8,6,0,1,4,0,9,2,3,5,0,8,6,0,例,从,0-2,的最短路径？,2024/9/13,77,以上所给出的求解最短路径的算法不仅适用于带权有向图，,对带权无向图也可以适用,。因为带权无向图可以看作是有往返二重边的有向图，只要在顶点,v,i,与,v,j,之间存在无向边,(,v,i,v,j,),，就可以看成是在这两个顶点之间存在权值相同的两条有向边,和,。,Floyd,算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路。,2024/9/13,78,