《数据结构》算法实现及解析- 数据结构07

2017/12/27,1,第7章 图,本章主题：图的基本概念、图的存储结构和图的常用算法 教学目的：教学重点：图的各种存储方式及其运算 教学难点：图结构存储方式的选择，几种经典图算法的实现 本章内容：图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径,2017/12/27,2,本章主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。通过本章学习，读者应该： 1) 了解图的定义和术语 2) 掌握图的各种存储结构 3) 掌握图的深度优先搜索和广度优先搜索遍历算法 4) 理解最小生成树、最短路径、拓扑排序、关键路径等图的常用算法,本章学习导读,2017/12/27,3,图（Graph）是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。 在线性结构中，结点之间的关系是线性关系，除开始结点和 终端结点外，每个结点只有一个直接前趋和直接后继。 在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。 在图结构中，对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。 由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。,2017/12/27,4,7. 1 .1 图的定义 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V, R ) V = x | x 某个数据对象 ， 是顶点的有穷非空集合； R边的有限集合 R = (x, y) | x, y V 无向图 或 R = | x, y V & Path (x, y)有向图 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。x弧尾，y弧头。,7.1 图及其基本运算,2017/12/27,5,有向图与无向图 有向图中：边用表示，且x与y是有序的。 a. 有向图中的边称为“弧” b. x弧尾或初始点 y弧头或终端点无向图：边用(x, y) 表示，且顶x与 y是无序的。完全图 在具有n 个顶点的有向图中，最大弧数为 n(n-1) 在具有n 个顶点的无向图中，最大边数为 n(n-1)/2顶点的度无向图：与该顶点相关的边的数目有向图： 入度ID(v) ：以该顶点为头的弧的数目 出度OD(v) ：以该顶点为尾头的弧的数目 在有向图中, 顶点的度等于该顶点的入度与出度之和。,2017/12/27,6,图7-1 无向图和有向图,2017/12/27,7,在图7-1中，图(a)为无向图，其中G1的顶点集合和边集合分别为：V(G1)=1，2，3，4，5，6，7，E(G1)=(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)。 图(c)为有向图，其中G3的顶点集合和弧集合分别为V(G3)=1，2，3，4，5，6，E(G3)=，,2017/12/27,8,7.1.2 图的基本术语1 顶点的度 与顶点v相关的边或弧的数目称作顶点v的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。 例如图7-1中，无向图G1中顶点3的度为4，顶点5的度为3。 例如在图7-1中，有向图G3中顶点1的出度OD (1)=3，入度ID (1)=1，其度TD (1)=4。,2017/12/27,9,2路径和回路 在无向图G中，若存在一个顶点序列Vp ,Vi1，Vi2，Vin，Vq, 使得（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。 若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。 起点和终点相同的路径称为回路； 简单路径组成的回路称为简单回路。 路径长度 路径上经过的边的数目称为该路径的路径长度。非带权图的路径长度是指此路径上边/弧的条数。带权图的路径长度是指路径上各边/弧的权之和。,2017/12/27,10,简单路径 若路径上各顶点 v1,v2,.,vm 均不互相重复, 则称这样的路径为简单路径。回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。,2017/12/27,11,3.边和弧边: 无向图中顶点的偶对，写成（Vx，Vy）或（Vy，Vx）。弧: 有向图中顶点的偶对,Vx,Vy表示从Vx到Vy。弧头: 弧的终点弧尾: 弧的起点,弧 Vx，Vy 弧尾Vx 弧头Vy,2017/12/27,12,4子图 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。,2017/12/27,13,图7-3 连通分量和强连通分量,5连通性 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点vi和vj（vi，vjV）都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 图7-1中G1是连通图，G2是非连通图。 G2中有3个连通分量，如图7-3（a）所示。 6 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,2017/12/27,14,7网络权 某些图的边或弧具有与它相关的数, 称之为权。权可以代表一个顶点到另一个顶点的距离，耗费等。网络 这种带权连通图图一般称为网络。如图7-4所示。,2017/12/27,15,8生成树、生成森林生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。 生成树是对连通图而言的 是连同图的极小连同子图 包含图中的所有顶点 有且仅有n-1条边 非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。,2017/12/27,16,9邻接点顶点: 图中的结点 邻接点:无向图中，若边(x,y)E，两顶点之间有条边，则两顶点互 为邻接点。 x y ( x ,y )有向图中，若弧(x,y)E，从x到y有一条弧，则y是x的邻接点， 但x不是y的邻接点。 x y ,2017/12/27,17,7.1.3 图的基本运算 图的基本运算也包括查找、插入和删除。（1）顶点定位运算 确定顶点v在图中的位置；（2）取顶点运算 求取图中第i个顶点；（3）求第一个邻接点运算 求图中顶点v的第一个邻接点；（4）求下一个邻接点运算 已知w为图中顶点v的某个邻接点，求顶点w的下一个邻接点；（5）插入顶点运算 在图中增添一个顶点v作为图的第n+1个顶点，其中n为插入该顶点前图的顶点个数；（6）插入弧运算 在图中增添一条从顶点v到顶点w的弧。（7）删除顶点运算 从图中删除顶点v以及所有与顶点v相关联的弧。（8）删除弧运算 从图中删除一条从顶点v到顶点w的弧。,2017/12/27,18,7.2.1 邻接矩阵 邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。设G(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵。,7.2 图的存储结构,无向图的邻接矩阵是以主对角线对称的，有向图的邻接矩阵可能是不对称的。 在有向图中： 第 i 行 1 的个数就是顶点 i 的出度， 第 j 列 1 的个数就是顶点 j 的入度。 在无向图中, 第 i 行 (列) 1 的个数就是顶点i 的度。,2017/12/27,19,图7-6 有向图及其邻接矩阵,图7-5 无向图及其邻接矩阵,2017/12/27,20,对于无向图，（vi，vj）和（vj，vi）表示同一条边，因此，在邻接矩阵中Aij=Aji。 无向图的邻接矩阵是（关于主对角线）对称矩阵，可用主对角线以上（或以下）的部分表示。 对有向图，弧和表示方向不同的两条弧，Aij和Aji表示不同的弧，所以有向图的邻接矩阵一般不具有对称性。 邻接矩阵表示法适合于以顶点为主的运算。,2017/12/27,21,对于有向图，顶点vi的出度OD (vi)等于邻接矩阵第i行元素之和；顶点vi的入度ID (vi)等于邻接矩阵第i列元素之和，即 ：,对于无向图，顶点vi的度等于邻接矩阵第i行的元素之和，即：,OD (vi)=,ID (vi)=,TD（vi）=,对于带权图的邻接矩阵，定义为：,2017/12/27,22,顶点表: 一个记录各个顶点信息的一维数组， 邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。 使用邻接矩阵存储结构，可用一维数组表示图的顶点集合，用二维数组表示图的顶点之间关系（边或弧）的集合，数据类型定义如下： #define MAX_VERTEX_NUM 20 /最大顶点数typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; /邻接矩阵类型typedef struct VertexType vexsMAX_VERTEX_NUM; /顶点表AdjMatrix arcs; /邻接矩阵int vexnum,arcnum; /图的顶点数和弧数 MGraph; 由于一般图的边或弧较少，其邻接矩阵的非零元素较少，属稀疏矩阵，因此会造成一定存储空间的浪费。,2017/12/27,23,建立邻接矩阵算法:void CreateMGraph(MGraph ,j=LocateVex(G,v2); G.arcsij=w; G.arcsji=w; return; ,2017/12/27,24,void PrintMGraph(MGraph G) /输出 int i,j;printf(Output Vertices:);printf(%s,G.vexs); printf(n);printf(Output AdjMatrix:n);for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+) printf(%4d,G.arcsij);printf(n); return; ,2017/12/27,25,7.2.2 邻接表 图的链式存储结构 1) 为每个顶点建立一个单链表， 2) 第i个单链表中包含顶点Vi的所有邻接顶点。 邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。,2017/12/27,26,把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点（边结点），邻接点域adjvex保存与该边相关联的另一顶点的顶点下标 ， 链域nextarc存放指向同一链表中下一个表结点的指针 ，数据域info存放边的权。边链表的表头指针存放在头结点中。头结点以顺序结构存储，其数据域data存放顶点信息，链域firstarc指向链表中第一个顶点。,2017/12/27,27,带权图的边结点中info保存该边上的权值 。 顶点 Vi 的边链表的头结点存放在下标为 i 的顶点数组中。 在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。 建立邻接表的时间复杂度为O(n*e)。若顶点信息即为顶点的下标，则时间复杂度为O(n+e)。,2017/12/27,28,有向图的邻接表和逆邻接表,在有向图的邻接表中，第 i 个链表中结点的个数是顶点Vi的出度。在有向图的逆邻接表中，第 i 个链表中结点的个数是顶点Vi 的入度。,2017/12/27,29,图7-7 为图7-6 (a)的的邻接表和逆邻接表,图7-7 有向图的邻接表和逆邻接表,7-6 (a),2017/12/27,30,网络 (带权图) 的邻接表,2017/12/27,31,存储表示typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;int info;ArcNode; /边结点类型typedef struct VNodeVertexType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM; typedef structAdjList vertices; /邻接表int vexnum,arcnum;ALGraph;,2017/12/27,32,int LocateVex(ALGraph G,char u) int i;for (i=0;iadjvex) DFS(G,p-adjvex); p=p-nextarc; /从第v个顶点出发DFS,2017/12/27,46,整个图的DFS遍历void DFSTraverse(ALGraph G) for (int v=0;vG.vexnum;+v) visitedv=0; for (v=0;v0 do(i)delete(Queue,f,r,x); /队首元素出队并赋于x(ii)对所有x的邻接点w if visitedw=0 then（a）访问w;（b）visitedw=1; （c）insert(Queue,f,r,w); /w进队列,2017/12/27,51,以邻接表为存储结构，广度优先搜索遍历算法如下：#define MAXV void bfs(ALGraph *g,int v) ArcNode *p; int queueMAXV; /定义存放队列的数组 int visitedMAXV； /定义存放结点的访问标志的数组 int f=0,r=0,x,i; /队列头尾指针初始化，把队列置空 for(i=0,in;i+) /访问标志数组初始化 visitedi=0; printf(“d”,v); /访问初始顶点v visitedv=1; /置已访问标记 r=(r+1)MAXV; queuer=v; /v进队 while(f!=r) /若队列不空时循环 f=(f+1)MAXV; x=queuetf; /出队并赋给x p=g-adjlistx.firstarc; /找与顶点x邻接的第一个顶点,2017/12/27,52,p=g-adjlistx.firstarc; /找与顶点x邻接的第一个顶点 while(p!=NULL) if (visitedp-adjvex=0) /若当前邻接点未被访问 visitedp-adjvex=l; /置该顶点已被访问的标志 printf(“d”，p-adjvex); /访问该顶点 r=(r+1)MAXV; queuer=p-adjvex; /该顶点进队 p=p-nextarc; /找下一个邻接点 / w进队列,2017/12/27,53,算法分析：,如果使用邻接表表示图，则循环的总时间代价为 d0 + d1 + + dn-1 = O(e)，其中的 di 是顶点 i 的度。如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的 n 个元素，总的时间代价为O(n2)。,2017/12/27,54,7.4 最小生成树,1. 生成树 在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G 称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同，例如图7-12的(b) 和(c) 为图7-12 (a) 的两棵生成树。其中 (b) 是通过DFS得到的，称为深度优先生成树；(c) 是通过BFS得到的，称为广度优先生成树。,图7-12 生成树,2017/12/27,55,按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。而所有包含n-1 条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图. 由于使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树 在图论中，常常将树定义为一个无回路连通图。 对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。,2017/12/27,56,假设把n个城市看作图的n个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接n个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生成树的算法有很多，下面分别介绍克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。,7.4.1 克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。,2017/12/27,57,算法的基本思想： 在图中任取一个顶点K作为开始点，令U=k，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离, 使之保持最小，再重复此过程，直到W为空集止。 假设G=（V，E）是一个具有n个顶点的带权无向连通图，T= (U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造最小生成树的过程如下：(1) 置U的初值等于V，TE的初值为空集；(2) 按权值从小到大的顺序依次选取图G中的边，若选取的边未使生成树T形成回路，则加入TE；若选取的边使生成树T形成回路，则将其舍弃。循环执行(2)，直到TE中包含(n-1)条边为止。,2017/12/27,58,应用克鲁斯卡尔算法构造最小生成树的过程:,2017/12/27,59,为实现克鲁斯卡尔算法需要设置一维辅助数组E，按权值从小到大的顺序存放图的边，数组的下标取值从0到e-1（e为图G边的数目）。 假设数组E存放图G中的所有边，且边已按权值从小到大的顺序排列。n为图G的顶点个数，e为图G的边数。克鲁斯卡尔算法如下：#define MAXE #define MAXV typedef struct int vex1; /边的起始顶点int vex2; /边的终止顶点int weight; /边的权值Edge;,2017/12/27,60,Void kruskal(Edge E,int n,int e) int i,j,m1,m2,sn1,sn2,k; int vsetMAXV; for(i=0;in;i+) /初始化辅助数组 for(i=0;in;i+) /初始化辅助数组 vseti=i; k=1; /表示当前构造最小生成树的第k条边，初值为1 j=0; /E中边的下标，初值为0 while(ke) /生成的边数小于e时继续循环 ml=Ej.vex1;m2=Ej.vex2;/取一条边的两个邻接点 sn1=vsetm1;sn2=vsetm2; /分别得到两个顶点所属的集合编号 if(sn1!=sn2) /两顶点分属于不同的集合，该边是最小生成树的一条边,2017/12/27,61, printf(“(m1，m2)：dn”,Ej.weight); k+; /生成边数增l for(i=0;in;i+) /两个集合统一编号 if (vseti= /集合编号为sn2的改为sn1 vseti=sn1; j+; /扫描下一条边 ,如果给定带权无向连通图G有e条边，且边已经按权值递增的次序存放在数组E中，则用克鲁斯卡尔算法构造最小生成树的时间复杂度为O (e)。克鲁斯卡尔算法的时间复杂度与边数e有关，该算法适合于求边数较少的带权无向连通图的最小生成树。,2017/12/27,62,7.4.2 普里姆(Prim)算法 普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。 从连通网络 N = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。,2017/12/27,63,假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造G的最小生成树T的步骤如下： （1）初始状态，TE为空，U=v0，v0V； （2）在所有uU，vV-U的边(u，v) E中找一条代价最小的边(u，v)并入TE，同时将v并入U；重复执行步骤（2）n-1次，直到U=V为止。 在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。 对于每一个顶点vV-U，closestv为U中距离v最近的一个邻接点，即边 (v，closestv) 是在所有与顶点v相邻、且其另一顶点jU的边中具有最小权值的边，其最小权值为lowcostv，即lowcostv=costvclosestv，,2017/12/27,64,采用邻接表作为存储结构：设置一个辅助数组closedge： lowcost域 存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值； adjvex域 记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。,设置一个辅助数组closedge： lowcost域：存放在V-U中各个顶点到集合U中的当前最小权值； adjvex域： 记录该边所依附的在U中的顶点,2017/12/27,65,若选择从顶点0出发，即u0 = 0，则辅助数组的两个域的初始状态为：然后反复做以下工作： 在 closedge i中选择 adjvex 0 & lowcost最小的边 i 用 k 标记它。则选中的权值最小的边为 (closedgek, G.vexsk)，相应的权值为 closedgek.lowcost。 将 closedgek.adjvex 改为 0, 表示它已加入生成树顶点集合。将边 (closedgek, G.vexsk)加入生成树的边集合。,2017/12/27,66,取 lowcosti = min lowcosti, G.arcski ，即用生成树顶点集合外各顶点 i 到刚加入该集合的新顶点 k 的距离 G.arcski 与原来它们到生成树顶点集合中顶点的最短距离lowcosti 做比较, 取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。 如果生成树顶点集合外顶点 i 到刚加入该集合的新顶点 k 的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改adj：adjvex = v。表示生成树外顶点i到生成树内顶点k当前距离最近。,2017/12/27,67,利用普里姆算法建立最小生成树:typedef int VRType;structVertexType adjvex;VRType lowcost; closedgeMAX_VERTEX_NUM;void MiniSpanTree_PRIM(MGraph G,VertexType u)int k,j,i,minCost;k=LocateVex(G,u);for (j=0;jG.vexnum;+j)if (j!=k) closedgej.adjvex=u;closedgej.lowcost=G.arcskj; ,2017/12/27,68,closedgek.lowcost=0; for (i=1;iG.vexnum;+i) k=minimum(closedge); minCost=INFINITY; for (j=0;jG.vexnum;+j) if (closedgej.lowcost minCost ,2017/12/27,69,普里姆算法中的第二个for循环语句频度为n-1，其中包含的两个内循环频度也都为n-1，因此普里姆算法的时间复杂度为O(n2)。普里姆算法的时间复杂度与边数e无关，该算法更适合于求边数较多的带权无向连通图的最小生成树。,2017/12/27,70,7.5 最短路径,交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通? 在有多条通路的情况下，哪一条路最短? 交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。 另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路(从其它顶点达到)。 路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。,2017/12/27,71,最短路径： 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 对于带权的图，通常把一条路径上所经过边或弧上的权值之和定义为该路径的路径长度。从一个顶点到另一个顶点可能存在着多条路径，把路径长度最短的那条路径称为最短路径，其路径长度称为最短路径长度。无权图实际上是有权图的一种特例，我们可以把无权图的每条边或弧的权值看成是l，每条路径上所经过的边或弧数即为路径长度。本章讨论两种最常见的最短路径问题。,2017/12/27,72,问题解法 边上权值非负情形的单源最短路径问题 Dijkstra算法所有顶点之间的最短路径 Floyd算法边上权值非负情形的单源最短路径问题 问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。,2017/12/27,73,7.5.1 求一顶点（单源点）到其余顶点的最短路径 单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。 迪杰斯特拉(Dijkstra)在做了大量观察后,首先提出了按路径长度递增产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法。 算法的基本思想是:设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。,2017/12/27,74,具体做法是:设源点为Vl,则S中只包含顶点Vl，令W=V-S，则W中包含除Vl外图中所有顶点，Vl对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧则Vj顶点的距离为此弧权值，否则为(一个很大的数)，然后每次从W中的顶点中选一个其距离值为最小的顶点Vm加入到S中，每往S中加入一个顶点Vm，就要对W中的各个顶点的距离值进行一次修改。若加进Vm做中间顶点，使+的值小于值，则用+代替原来Vj的距离，修改后再在W中选距离值最小的顶点加入到S中，如此进行下去，直到S中包含了图中所有顶点为止。,2017/12/27,75,图7-16 带权有向图,设G=(V，E)是一个带权有向图，指定的顶点v0为源点，求v0到图的其余各顶点的最短路径。如图7-16所示，若以顶点0为v0，它到其余各顶点的最短路径分别为：顶点0 顶点1：无路径顶点0 顶点2：最短路径为（0，2），最短路径长度为10顶点0 顶点4：最短路径为（0，4），最短路径长度为30顶点0 顶点3：最短路径为（0，4，3），最短路径长度为50顶点0 顶点5：最短路径为（0，4，3，5），最短路径长度为60,2017/12/27,76,从以上图7-16的最短路径可以看出：(1) 最短路径并不一定是经过边或弧数最少的路径。如从顶点0到顶点5的路径（0，5）长度为100，路径（0，4，5）长