图的存储与Dijkstra算法求最短路径PPT学习课件

1、图的存储与Dijkstra算法求最短路径,1,2,什么是图,2,2020/7/1,图的分类,有向图 带权有向图 无权有向图 无向图 带权无向图 有权无向图,3,2020/7/1,图的表示方法,邻接矩阵 邻接表 前向星,4,2020/7/1,图的邻接矩阵表示法,对于有n个顶点的图，用一维数组vexsn存储顶点信息，用二维数组Ann存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素Aij存放的是顶点i到顶点j之间关系的信息。,5,2020/7/1,无向无权图的邻接矩阵表示,6,2020/7/1,无向带权图的邻接矩阵表示,7,2020

2、/7/1,有向无权图的邻接矩阵,8,2020/7/1,有向带权图的邻接矩阵,9,2020/7/1,图的邻接表表示法,链表中的结点称为表结点，每个结点由三个域组成，如图7-9(a)所示。其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号)，链域(nextarc)指向下一个与顶点Vi邻接的表结点，数据域(info)存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。每个链表设一个表头结点(称为顶点结点)，由两个域组成，如图7-9(b)所示。链域(firstarc)指向链表中的第一个结点，数据域(data) 存储顶点名或其他信息。,10,20

3、20/7/1,无向无权图的邻接表表示法,表示空指针,11,2020/7/1,前向星,数组下标： 1 2 3 4 5 6 7 8 9 10 11,0 0 1 0 3 0 2 6 4 8,2 1 3 1 4 1 4 2 4 3,5 7 9 10,next：,to：,head：,依次存储的边为：(1，2)、(2，1)、(1，3)、(3，1)、(1，4)、(4，1) (2，4)、(4，2)、(3，4)、(4，3),12,2020/7/1,图的遍历,深度优先遍历(DFS) 广度优先遍历(BFS),13,2020/7/1,图的最小生成树,如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值

4、之和称为生成树的代价。最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。,14,2020/7/1,求最小生成树的算法,普里姆(Prim)算法 克鲁斯卡尔(Kruskal)算法,15,2020/7/1,普里姆(Prim)算法求最小生成树的过程,16,2020/7/1,克鲁斯卡尔(Kruskal)算法求最小生成树的过程,17,2020/7/1,求最短路径,求单源最短路径：Dijkstra（迪杰斯特拉）算法，时间复杂度O(n2) 求全局最短路径：Floyd算法，时间复杂度O(n3) 使用者两种算法的条件：要求必须是无环图,18,2020/7/1,

5、Dijkstra算法（求顶点A到其他顶点的最短距离）,算法思想如下： 初始化源点A到其他顶点的距离，若其他顶点与源点A无直接相连的边，则认为源点A到该顶点的距离为无穷大（程序中使用int或long long的最大值表示无穷大）； 选择当前距离源点A最近的顶点X（注意：顶点X必须未被选择过）； 以X点为参照，更新源点A到其他未被选择过的点M的距离 若A-X-M小于A-M距离，则使用新距离替换原距离； 若A-X-M大于等于A-M距离，则保持原距离不变； 重复步骤2、3，直到选取完所有的点为止。,19,2020/7/1,求解过程： 初始化源点A到 B、C、D、E、F、G、H、I 的路径长度 从 B、

6、C、D、E、F、G、H、I 中选择到源点A距离最小的顶点，该顶点为B 以B为参照更新源点A到 C、D、E、F、G、H、I 的路径长度 如果新路径长度小于原长度，则用新的长度作为A到该点的路径长度 基于新的路径长度，重复步骤2、3。选择距离A点最近且未被选择过的点，直到选取完所有点,Dijkstra算法（求A到其他顶点的最短距离，注：*表示无穷大）第1步,3,4,3,*,6,*,*,4,*,*,B,A-B- C 路径长度为4 (4 B- D 路径长度为* (*等于*),*,A-B- E 路径长度为* (*等于*),*,A-B- F 路径长度为* (* 6),6,A-B- G 路径长度为* (*

7、4),4,A-B- H 路径长度为10 (10B-I 路径长度为* (*等于*),*,20,2020/7/1,Dijkstra算法（求A到其他顶点的最短距离，注：*表示无穷大） 第2步,求解过程： 继续从 C、D、E、F、G、H、I（需排除上一轮已被选择过的顶点B） 中选择距源点A最近的点C 以点C为参照更新源点A到 D、E、F、G、H、I 的路径长度 如果新路径长度小于原路径长度，则用新的长度作为A到该点的路径长度 基于新的路径长度，重复步骤1、2。,3,4,3,*,6,*,*,4,*,*,B,*,*,6,4,10,*,C,3,4,A-(B)-C-D 路径长度为：4 + 8 = 12 (12

8、 C-E 路径长度为：4 + * = * (* = *),*,A-(B)-C-F 路径长度为：4 + 1 = 5 (5C-G 路径长度为：4 + 2 = 6 (64),4,A-(B)-C-H 路径长度为：4 + * = * (*10),10,A-(B)-C-I 路径长度为：4 + 9 = 13 (13G-D 路径长度为：4 + * = * (* 12),4,继续从 D、E、F、G、H、I 中选择距源点A最近的点G（需排除前2轮已选择过的顶点B、C） 参照G更新源点A到 D、E、F、H、I 的路径长度,4,12,A-G-E 路径长度为：4 + * = * (* = *),*,A-G-F 路径长度

9、为：4 + * = * (* 5),5,A-G-H 路径长度为：4 + 4 = 8 (8 G-I 路径长度为：4 + * = * (* 13),13,22,2020/7/1,Dijkstra算法（求A到其他顶点的最短距离，注：*表示无穷大） 第4步,A-(B、C)-F-D 路径长度为：5 + * = * (* 12),继续从 D、E、F、H、I 中选择距源点A最近的点F（需排除前3轮已选择过的顶点B、C、G） 参照F更新源点A到 D、E、H、I 的路径长度,F,12,A-(B、C)-F-E 路径长度为：5 + * = * (* = *),*,A-(B、C)-F-H 路径长度为：5 + 2 =

10、7 (7 F-I 路径长度为：5 + * = * (* 13),13,23,2020/7/1,Dijkstra算法（求A到其他顶点的最短距离，注：*表示无穷大） 第5步,A-(B、C、F)-H-D 路径长度为：7 + 3 = 10 (10 H-E 路径长度为：7 + * = * (* = *),*,A-(B、C、F)-H-I 路径长度为：7 + 4 = 11 (11 D-E 路径长度为：10 + 5 = 15 (15 D-I 路径长度为：10 + * = * (* 11),11,25,2020/7/1,Dijkstra算法（求A到其他顶点的最短距离，注：*表示无穷大） 第7步,A-(B、C、F、H)-I-E 路径长度为：11 + 4 = 15 (15 = 15),1、继续从 E、I 中选择距源点A最近的点I（需排除前6轮已选择过的顶点B、C、D、F、G、H）,F,12,*,7,13,H,10,*,11,D,15,11,15,I,2、参照I