数据结构和算法分析第6讲-图课件.ppt

1、Chapter 6Graphs图的类型定义图的类型定义 n(n0)个元素的有个元素的有限集合限集合基基 本本 术术 语语 图图是由一个是由一个顶点集顶点集V和一个和一个弧集弧集VR构构 成的数据结构成的数据结构 Graph=(V,VR)其中其中:VR|v,wV 且且 P(v,w)表示从表示从 v 到到 w 的一条弧，并称的一条弧，并称 v 为为弧尾弧尾，w 为为弧头弧头 谓词谓词 P(v,w)定义了弧定义了弧 的意义的意义或信息或信息 由于由于“弧弧”是有方向的，因此称由是有方向的，因此称由 顶点集和弧集构成的图为顶点集和弧集构成的图为有向图有向图 AB E C D 例如例如:G1=(V1,V

2、R1)其中其中:V1=A,B,C,D,EVR1=,若有若有 VR,必必有有 VR,则称则称(v,w)为顶点为顶点v和顶和顶点点w之间存在一条之间存在一条边边 B CA D F E由顶点集和边集构由顶点集和边集构成的图称作成的图称作无向图无向图例如例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=,名词和术语名词和术语网、子图网、子图 完全图完全图、稀疏图、稠密图稀疏图、稠密图邻接点、度、入度、出度邻接点、度、入度、出度路径、路径长度、简单路径路径、路径长度、简单路径、简单回路简单回路连通图、连通分量、连通图、连通分量、强连通图、强连通分量强连通图、强连通分量生成树、生成森林生成树

3、、生成森林关节点、重连通图关节点、重连通图重连通分量、连通度重连通分量、连通度AEFBBC设图设图G=(V,VR)和和图图G=(V,VR ),且且VV,VRVR,则则称称 G 为为 G 的的子图子图ABECF1597211132弧或边带权的图分弧或边带权的图分别称作别称作有向网有向网或或无无向网向网假设图中有假设图中有 n 个顶点，个顶点，e 条边，则条边，则 含有含有 e=n(n-1)/2 条边的无向图称条边的无向图称作作无向完全图无向完全图 含有含有 e=n(n-1)条弧的有向图称条弧的有向图称作作有向完全图有向完全图 若边或弧的个数若边或弧的个数 enlogn，则称，则称作作稀疏图稀疏图

4、，否则称作，否则称作稠密图稠密图 假若顶点假若顶点v 和顶点和顶点w 之间存在一条之间存在一条边，则称顶点边，则称顶点v和和w互为互为邻接点邻接点，边，边(v,w)(v,w)ID(B)=3ID(A)=2和顶点和顶点v和和w相相关联关联 和顶点和顶点v 关联的边的数目定义为顶关联的边的数目定义为顶点的点的度度ACDFEB顶点的顶点的出度出度:以顶点以顶点v为弧尾的弧的数目为弧尾的弧的数目ABECF有向图有向图顶点的顶点的入度入度:以顶点以顶点v v为弧头的弧的数目为弧头的弧的数目顶点的顶点的度度(TD)=)=出度出度(OD)+)+入度入度(ID)ID(B)=2OD(B)=1TD(B)=3设图设图

5、G=(V,VR)中的一个顶点序列中的一个顶点序列 u=vi,0,vi,1,vi,m=w中中，(vi,j-1,vi,j)VR 1jm,则称从顶点则称从顶点u 到顶点到顶点w 之之间存在一条间存在一条路径路径。路径上。路径上边的数目称作边的数目称作路径长度路径长度ABECF长度为长度为3的路径的路径A,B,C,FABECF简单路径简单路径:序列中顶点序列中顶点不重复出现的路径不重复出现的路径简单回路简单回路:序列中第一序列中第一个顶点和最后一个顶个顶点和最后一个顶点相同的路径点相同的路径若图若图G中任意两个中任意两个顶点之间都有路径顶点之间都有路径相通，则称此图为相通，则称此图为连通图连通图若无向

6、图为非连通若无向图为非连通图，则图中各个极图，则图中各个极大连通子图称作此大连通子图称作此图的图的连通分量连通分量BACDFEBACDFE 若任意两个顶点之间若任意两个顶点之间都存在一条有向路径，则称此有向图都存在一条有向路径，则称此有向图为为强连通图强连通图,ABECFABECF对有向图，对有向图，否则，其各个强连通子否则，其各个强连通子图称作它的图称作它的强连通分量强连通分量假设一个连通图有假设一个连通图有n个顶点和个顶点和e条边，其条边，其中中n-1 条边和条边和n个顶点构成一个极小连通个顶点构成一个极小连通子图，称该极小连通子图为此连通图的子图，称该极小连通子图为此连通图的生成树生成树

7、对非连通图，则对非连通图，则称由各个连通分称由各个连通分量的生成树的集量的生成树的集合为此非连通图合为此非连通图的的生成森林生成森林BACDFE 没有关节点的连通图被称为没有关节点的连通图被称为重连重连通图通图 若连通图中的某个顶点和其相关若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称成两个或两个以上的连通分量，则称此顶点为此顶点为关节点关节点 一个连通图一个连通图G G如果不是重连通图，如果不是重连通图，那么它可以包括几个那么它可以包括几个重连通分量重连通分量 若依次删除一个连通图中的若依次删除一个连通图中的 1,

8、2,k-11,2,k-1个顶点后个顶点后,该图仍连通该图仍连通,删除第删除第k k个顶个顶点后该图成为不连通的点后该图成为不连通的,则称该图的则称该图的连通度连通度为为k k结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作顶点的遍历顶点的遍历插入和删除弧插入和删除弧基本操作基本操作CreatGraph(&G,V,VR):/按定义按定义(V,VR)构造图构造图DestroyGraph(&G):/销毁图销毁图结构的建立和销毁结构的建立和销毁对顶点的访问操作对顶点的访问操作LocateVex(G,u);/若若G中存在顶点中存在顶

9、点u，则返回该顶点在，则返回该顶点在/图中图中“位置位置”；否则返回其它信息；否则返回其它信息GetVex(G,v);/返回返回 v 的值的值PutVex(&G,v,value);/对对 v 赋值赋值value对邻接点的操作对邻接点的操作FirstAdjVex(G,v);/返回返回v的的“第一个邻接点第一个邻接点”。若该顶点。若该顶点 /在在G中没有邻接点，则返回中没有邻接点，则返回“空空”NextAdjVex(G,v,w);/返回返回v的（相对于的（相对于w的）的）“下一个邻接下一个邻接/点点”。若。若w是是v的最后一个邻接点，则的最后一个邻接点，则/返回返回“空空”插入或删除顶点插入或删除

10、顶点InsertVex(&G,v);/在图在图G中增添新顶点中增添新顶点vDeleteVex(&G,v);/删除删除G中顶点中顶点v及其相关的弧及其相关的弧插入和删除弧插入和删除弧InsertArc(&G,v,w);/在在G中增添弧中增添弧，若，若G是无向的，是无向的，/则还增添对称弧则还增添对称弧DeleteArc(&G,v,w);/在在G中删除弧中删除弧，若，若G是无向的，是无向的，/则还删除对称弧则还删除对称弧遍遍 历历DFSTraverse(G,v,Visit();/从顶点从顶点v起起深度优先深度优先遍历图遍历图G，并对每，并对每/个顶点调用函数个顶点调用函数Visit一次且仅一次一次

11、且仅一次BFSTraverse(G,v,Visit();/从顶点从顶点v起起广度优先广度优先遍历图遍历图G，并对每，并对每/个顶点调用函数个顶点调用函数Visit一次且仅一次一次且仅一次图的存储表示图的存储表示一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示二、图的邻接表存储表示二、图的邻接表存储表示四、有向图的十字链表存储表示四、有向图的十字链表存储表示 五、无向图的邻接多重表存储表示五、无向图的邻接多重表存储表示三、图的逆邻接表存储表示三、图的逆邻接表存储表示Aij=0 (i,j)VR1 (i,j)VR图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为有

12、向图的邻接矩有向图的邻接矩阵为非对称矩阵阵为非对称矩阵ABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0网（边或弧带权值的图）的数组(邻接矩阵)存储表示如下否则或如VRvvvvwAjijiijij),(,5935531822520 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE图的邻接表存储表示图的邻接表存储表示 0 1 2 3 4有向图的邻接表有向图的邻接表1 4230 12 A B C D EABECD可见，在有向图的可见，在有向图的邻接表中不易找到邻接表中不易找到指向该顶点的弧指向该顶

13、点的弧ABECD在有向图的在有向图的邻接表中，邻接表中，对每个顶点，对每个顶点，链接的是指链接的是指向该顶点的向该顶点的弧弧图的逆邻接表存储表示图的逆邻接表存储表示 A B C D E 033420 012341有向图的十字链表存储表示有向图的十字链表存储表示 弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧头有相同弧头的结点指向下一个有相同弧尾有相同弧尾的结点typedef struct ArcBox /弧的结构表示弧的结构表示 int tailvex,headvex;InfoType *info;struct ArcBox *hlink,*tlink;Ve

14、xNode;顶点的结点结构顶点的结点结构顶点信息数据 指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出弧第一条出弧typedef struct VexNode /顶点的结构表示顶点的结构表示 VertexType data;ArcBox *firstin,*firstout;VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM;/顶点结点(表头向量)int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)对右边所示的有向图G,十字链表表示如下:无向图的邻接多重表存储表

15、示typedef struct Ebox VisitIf mark;/访问标记 int ivex,jvex;/该边依附的两个顶点的位置 struct EBox *ilink,*jlink;InfoType *info;/该边信息指针 EBox;边的结构表示边的结构表示typedef struct /邻接多重表邻接多重表 VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;顶点的结构表示顶点的结构表示typedef struct VexBox VertexType data;EBox *firstedge;/指向第一条依附该顶点的

16、边 VexBox;无向图的结构表示无向图的结构表示对右边所示的无向图G,邻接多重表表示如下:图的遍历图的遍历前进前进回退回退ACDEGBFIHACDEGBFIH123456789123456789深度优先遍历过程深度优先遍历过程 深度优先生成树深度优先生成树ACDEGBFIHACDEGBFH123456789123456789广度优先遍历过程广度优先遍历过程 广度优先生成树广度优先生成树Ivoid traverse(int n,Graph g)for(v=0;v n;v+)visitedv=false;for(v=0;v n;v+)if(!visitedv)dfs(v,g)或或 bfs(v,g

17、);void dfs(int v,Graph g)cout=0;w=NextAdjVex(g,v,w)if(!visitedw)dfs(w,g)void bfs(int v,Graph g)cout=0;w=NextAdjVex(g,v,w)if(!visitedw)cout GetVex(g,w);EnQueue(q,w);visitedw =true;最小代价生成树最小代价生成树(minimum cost spanning tree)假设要在假设要在 n 个城市之间建立通讯个城市之间建立通讯联络网，则连通联络网，则连通 n 个城市只需要修建个城市只需要修建 n-1 条线路，条线路，如何在最

18、节省经费的前如何在最节省经费的前提下建立提下建立这个这个通讯网通讯网？问题问题 构造网的一棵最小生成树，即：构造网的一棵最小生成树，即：在在 e 条带权的边中选取条带权的边中选取n-1条边（不条边（不构成回路），使构成回路），使“权值之和权值之和”为最小为最小该问题等价于该问题等价于构造最小生成树的准则构造最小生成树的准则n必须使用且仅使用该网络中的必须使用且仅使用该网络中的n-1 条边来联结网络中的条边来联结网络中的 n 个顶点个顶点n不能使用产生回路的边不能使用产生回路的边n各边上的权值的总和达到最小各边上的权值的总和达到最小算法二：克鲁斯卡尔算法算法二：克鲁斯卡尔算法 算法一：普里姆算法

19、算法一：普里姆算法 (Prim)普里姆算法的普里姆算法的基本思想基本思想 1.取图中任意一个顶点取图中任意一个顶点 v 作为作为 生成树的根，之后往生成树生成树的根，之后往生成树 上添加新的顶点上添加新的顶点 w 2.在在生成树的构造过程中，图中生成树的构造过程中，图中 n 个个顶点分属两个集合：顶点分属两个集合：已落在生成树上的顶点已落在生成树上的顶点集集 U 和和尚未落在生成树上的顶点集尚未落在生成树上的顶点集V-U，则则应在所有连通应在所有连通U中顶点和中顶点和V-U中顶点的边中选中顶点的边中选取权值最小的边取权值最小的边(v,w)这里这里v属于属于V-U，w属于属于UUV-U 3.之后

20、继续往生成树上添加顶之后继续往生成树上添加顶 点，直至生成树上含有点，直至生成树上含有 n-1 个顶点为止个顶点为止abcdegf195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和=14+8+3+5+16+21=67Template int MinVerTex(const Algraph&g,int*adjVex)/返回返回W,边边为连接为连接V-U到到U的最小权值的边的最小权值的边 int w=-1;int v;for(v=0;v0 w=v;break;for(v+;v0&g.GetWeight(v,adjVerv g.GetWeight(w

21、,adjVerw)w=v;return w;Template void MinSpanTreeprim(const Algraph&g,int u0)/从从u0出发构造网出发构造网G的最小代价生成树的最小代价生成树 assert(u0)=0&u0g.NumVex();int*adjVex;int u,v,w;adjVex=new intg.NumVex()for(v=0;vg.NumVer();v+)if(v!=u0)adjVexv=u0;g.SetTag(v,UNVISITED);else g.SetTag(v,VISITED);adjVexv=u0;/初始化辅助数组初始化辅助数组adjVe

22、x,并对顶点作标志并对顶点作标志 for(u=1;ug.NumVer();v+)/选择生成树的其余选择生成树的其余g.NumVex()-1个顶点个顶点 w=MinVerTex(g,*adjVex);if(w=-1)return countadjVexw=0;v=g.NumAdjVex(w,v)/新顶点并入新顶点并入U后从新选择最小边后从新选择最小边 if(g.Tag(v)=UNVISITED&(g.GetWeight(v,w)g.GetWeight(v,adjVerv)g.GetWeight(v,adjVerv)=0)adjVexv=w;/为新最小的边为新最小的边 Delete adjVex;

23、252510504613228102514242216185046132504613210原图 (a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212克鲁斯卡尔算法的克鲁斯卡尔算法的基本思想基本思想具体做法具体做法:先构造一个只含先构造一个只含 n 个顶点的个顶点的子图子图 SG，然后从权值最小的边开始，然后从权值最小的边开始，若它的添加不使若它的添加不使SG 中产生回路，则在中产生回路，则在 SG 上加上这条边，如此重复，直至加上加上这条边，如此重复，直至加上上 n-1 条边为止条边为止考虑问题的出发点考虑问题的出发

24、点:为使生成树上为使生成树上边边的权值之和达到最小的权值之和达到最小，则应使生成树，则应使生成树中每一条边的权值尽可能地小中每一条边的权值尽可能地小abcdegf195141827168213ae12dcbgf7148531621712181910504613228102514242216181250461325046132原图 (a)(b)1012504613228102514242216181250461325046132101412原图 (c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123学生课程学习工程图学

25、生课程学习工程图C8C3C5C4C9C6C7C1C2拓扑排序拓扑排序(TopologicalSort)按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系 由此所得顶点的线性序列称之为拓扑有序序列例如：对于下列有向图例如：对于下列有向图BDAC可求得可求得拓扑有序序列拓扑有序序列：A B C D 或或 A C B DBDAC反之，对于下列有向图反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路因为图中存在一个回路 B,C,D进行拓扑排序的步骤进行拓扑排序的步骤一、从有向图中选取一个没有前驱一、从有向图中选取一个没

26、有前驱 的顶点，并输出之的顶点，并输出之 重复上述两步，直至图空，或者重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止图不空但找不到无前驱的顶点为止二、从有向图中删去此顶点以及所二、从有向图中删去此顶点以及所 有以它为尾的弧有以它为尾的弧abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点 删除顶点及以它为尾的弧删除顶点及以它为尾的弧 弧头顶点的入度减弧头顶点的入度减1C8C3C5C4C9C6C7C1C2C0C1C2C3C4C5(a)有向无环图有向无环图C2C5C1C0

27、C3(b)输出顶点输出顶点C4C1C2C5C3(c)输出顶点输出顶点C0C4C0C2C5C1C3(d)输出顶点输出顶点C3C1C2C5(e)输出顶点输出顶点C2C5C1(f)输出顶点输出顶点C1C5(g)输出顶点输出顶点C5(h)拓扑排序完成拓扑排序完成在算法中在算法中,使用一使用一个个堆栈堆栈或或队列队列存放入度存放入度为零的顶点为零的顶点,供选择和供选择和输出无前驱的顶点输出无前驱的顶点012345C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0count data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0指向新栈顶指向新栈顶

28、 原栈顶元素在原栈顶元素在中中退到次退到次 栈顶栈顶C0C1C2C3C4C513010313112322-112221-1222012345012345012345012345toptoptoptoptoptoptoptopC0C1C2C3C4C52112222112212-1-122-12-1-122-1012345012345012345012345toptoptoptoptoptopvoid Graph:TopologicalSort()int top=-1;/入度为零的顶点栈初始化入度为零的顶点栈初始化 for(int i=0;in;i+)/入度为零顶点入度为零顶点 if(counti

29、=0)/进栈进栈 counti=top;top=i;for(i=0;in;i+)/期望输出期望输出n个顶点个顶点 if(top=-1)/中途栈空中途栈空,转出转出 cout“网络中有回路！网络中有回路！endl;return;else /继续拓扑排序继续拓扑排序 int j=top;top=counttop;/退栈退栈 coutj-dest;/另一顶点另一顶点 if(-countk=0)/顶点入度减一顶点入度减一 countk=top;top=k;/顶点的入度减至零顶点的入度减至零,进栈进栈 p=p-link;关键路径关键路径问题问题:假设以有向网表示一个施工流程假设以有向网表示一个施工流程

30、图，弧上的权值表示完成该项子图，弧上的权值表示完成该项子 工程所需时间。工程所需时间。问：问：哪些子工程项是哪些子工程项是“关键工程关键工程”？即：即：哪些子工程项将影响整个工程的哪些子工程项将影响整个工程的 完成期限完成期限abcdefghk64521187244例如例如:整个工程完成的时间为整个工程完成的时间为：从有向图的：从有向图的源源点点到到汇点汇点的最长路径的最长路径源点汇点6174用有向边表示一个工程中的活动用有向边表示一个工程中的活动 (Activity),用边上权值表示活动持续用边上权值表示活动持续时间时间 (Duration),用顶点表示事件用顶点表示事件 (Event)“关

31、键活动关键活动”指的是：指的是：该弧上的该弧上的权值增加权值增加 将使有向图上的将使有向图上的最长路径的最长路径的长度增加长度增加完成整个工程所需的时间取决完成整个工程所需的时间取决于从源点到汇点的最长路径长于从源点到汇点的最长路径长度度,即在这条路径上所有活动即在这条路径上所有活动的持续时间之和的持续时间之和。这条路径长。这条路径长度最长的路径就叫做度最长的路径就叫做关键路径关键路径 如何求关键活动？如何求关键活动？假设第假设第 i i 条弧为条弧为 对第对第 j j 个顶点而言个顶点而言“事件事件(顶点顶点)”)”的最早发生时间的最早发生时间 veve(j j)“事件事件(顶点顶点)”)”

32、的最迟发生时间的最迟发生时间 vlvl(j j)对第对第 i i 项活动而言项活动而言“活动活动(弧弧)”)”的最早开始时间的最早开始时间 eeee(i i)“活动活动(弧弧)”)”的最迟开始时间的最迟开始时间 elel(i i)veve(源点源点)=0=0；veve(k k)=MaxMax veve(j j)+dutdut()(2 2=k k=n n,属于所有以属于所有以k k为为 头头的弧的集合的弧的集合)vlvl(汇点汇点)=veve(汇点汇点)；vlvl(j j)=MinMin vlvl(k k)dutdut()(1 1=j j=n-1n-1,属于所有以属于所有以j j为为 尾尾的弧的

33、集合的弧的集合)附注“事件(顶点)”的 最早发生时间 ve(j)ve(j)=从源点到顶点j的最长路径长度；“事件(顶点)”的 最迟发生时间 vl(k)vl(k)=从源点到汇点的最长路径长度-从顶点k到汇点的最长路径长度。eeee(i i)=veve(j j)elel(i i)=vlvl(k k)dutdut()veve(源点源点)=vlvl(源点源点)=0=0vlvl(汇点汇点)=veve(汇点汇点)关键活动关键活动:elel(i i)=eeee(i i)这两个递推公式的计这两个递推公式的计算必须分别在算必须分别在拓扑有序拓扑有序及及逆拓扑有序逆拓扑有序的前提下进行的前提下进行abcdefgh

34、k64521187244a b c d efg h kvevl0000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-ka b c d efg h kvevl06457715 14 18181416107866000064577715 14141602366887 10显然显然 求求ve的顺序应该是的顺序应该是按拓扑有序按拓扑有序的的 次序次序 而而 求求vl的顺序应该是的顺序应该是按拓扑逆序按拓扑逆序的的 次序次序因为因为 拓扑逆序序列即为拓扑有序序列拓扑逆序序列即为拓扑有序序

35、列 的的逆序列逆序列因此因此 应该在拓扑排序的过程中，应该在拓扑排序的过程中，另设一个另设一个“栈栈”记下拓扑有序序记下拓扑有序序列列求关键路径算法Status Topologicalorder(ALGraph G,Stack&T)/求各顶点的最早发生时间求各顶点的最早发生时间veFindInDegree(G,indegree);/求各顶点入度求各顶点入度);建零入度顶点栈建零入度顶点栈S;Initstack(S);count=0;Ve0.G.vexnum-1=0;/初始化初始化While(!StackEmpty(S)Pop(S,j);Push(T,j);+count;for(p=G.vert

36、icesj.firstarc;p;p=p-nesyarc)k=p-adjvex;if(-indegreek=0)Push(S,k);if(vej+*(p-info)vek)vek=vej+*(p-info);/for *(p-info)=dut()/while if(countG.vexnum)return ERROR;else return OK/依依最短路径的长最短路径的长度度递增的次序求得各递增的次序求得各条路径条路径源点源点v1 其中，从源其中，从源点到顶点点到顶点v的最的最短路径是所有最短路径是所有最短路径中长度最短路径中长度最短者短者v2 在这条路径上，必定只含一条弧，并且这条弧的

37、权值最小。下一条路径长度次短(第1次)的最短路径最短路径的特点：路径长度最短(第0次)的最短路径最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。其余最短路径(第k次)的特点：再下一条路径长度次短(第2次)的最短路径最短路径的特点:它可能有两种情况：或者是从源点不经过v2到该点；或者是从源点到顶点v2，再到达该顶点。它或者是从源点不经过vk到该点；或者是从源点到vk，再到达该顶点。求最短路径的迪杰斯特拉算法：设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。1）在所

38、有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Distk值。假设求得最短路径的顶点为u，若若 Distu+G.arcsukDistk则将 Distk 改为 Distu+G.arcsuk。INFINITYkvarcsGkDist0.V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。求每一对顶点之间的最短路径求每一对顶点之间的最短路径弗洛伊德算法的基本思想是：弗洛伊德算法的基本思想是：从从 v vi i 到到 v vj j 的所有可能存在的的所有可能存在的路径中，选出一条长度最短的路径路径中，选出一条长度最短的路径

39、顶点集为V=v1,v2,.vn第0步:若存在,则存在路径vi,vj/路径中不含其它顶点,相当于中间点集U=A0ij=G.arcsij(编程序时不写上标，即为Aij=G.arcsij)第1步:若,存在，则存在路径vi,v1,vj/路径中所含顶点序号不大于1,相当于中间点集U=v1A1ij=MINA0ij,A0i1+A01j第2步:若vi,v2,v2,vj存在，则存在一条路径vi,v2,vj/路径中所含顶点序号不大于2号,相当于中间点集U=v1,vnA1ij=MINA0ij,A0i1+A01j 第n步:若vi,vn,vn,vj存在，则存在一条路径vi,vn,vj/路径中所含顶点序号不大于n号,相当于中间点集U=V,为最短路径Anij=MINAn-1ij,An-1in+An-1nj