图的存储与Dijkstra算法求最短路径

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

图的存储与Dijkstra算法求最短路径什么是图图的分类•有向图•带权有向图•无权有向图•无向图•带权无向图•有权无向图图的表示方法•邻接矩阵•邻接表•前向星图的邻接矩阵表示法•对于有n个顶点的图,用一维数组vexs[n]存储顶点信息,用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中,以顶点在vexs数组中的下标代表顶点,邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。无向无权图的邻接矩阵表示1若(vi,vj)E,即vi,vj邻接0若(vi,vj)E,即vi,vj不邻接A[i][j]=(a)无向图abcd(b)顶点数组vexsabcd0111101111011110(c)邻接矩阵无向带权图的邻接矩阵表示(a)带权无向图(b)顶点数组(c)邻接矩阵354126abcde3vexsabcde∞62∞∞6∞34323∞1∞∞43∞5∞3∞5∞Wij若(vi,vj)E,即vi,vj邻接,权值为wij∞若(vi,vj)E,即vi,vj不邻接时A[i][j]=有向无权图的邻接矩阵(a)有向图acbde(b)顶点数组vexsabcde(c)邻接矩阵0110100000000111100000010有向带权图的邻接矩阵(b)顶点数组vexsabcde(c)邻接矩阵∞62∞∞∞∞∞∞3∞3∞1∞∞4∞∞5∞∞∞∞∞(a)带权有向图354126abcde3图的邻接表表示法链表中的结点称为表结点,每个结点由三个域组成,如图7-9(a)所示。其中邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号),链域(nextarc)指向下一个与顶点Vi邻接的表结点,数据域(info)存储和边或弧相关的信息,如权值等。对于无权图,如果没有与边相关的其他信息,可省略此域。每个链表设一个表头结点(称为顶点结点),由两个域组成,如图7-9(b)所示。链域(firstarc)指向链表中的第一个结点,数据域(data)存储顶点名或其他信息。adjvexinfonextarc表结点:datafirstarc顶点结点:图7-9邻接链表结点结构无向无权图的邻接表表示法v1v2v3v4v501234MAX_VEX-1v1v2v3v4┇┇v5213⋀02⋀0314⋀204⋀23⋀⋀表示空指针前向星1243数组下标:12345678910110010302648213141424357910next:to:head:依次存储的边为:(1,2)、(2,1)、(1,3)、(3,1)、(1,4)、(4,1)(2,4)、(4,2)、(3,4)、(4,3)图的遍历深度优先遍历(DFS)广度优先遍历(BFS)图的最小生成树如果连通图是一个带权图,则其生成树中的边也带权,生成树中所有边的权值之和称为生成树的代价。最小生成树(MinimumSpanningTree):带权连通图中代价最小的生成树称为最小生成树。求最小生成树的算法•普里姆(Prim)算法•克鲁斯卡尔(Kruskal)算法v1v3v2v4v54857121136(a)带权无向图如图所示v2v45(b)选择与v2相邻的边最小的顶点(c)v53v2v45(d)v14v53v2v45v36(e)v14v53v2v45普里姆(Prim)算法求最小生成树的过程克鲁斯卡尔(Kruskal)算法求最小生成树的过程v1v3v2v4v54857121136(a)(b)选择所有的边中权值最小的边3v5v4v36(e)v14v53v2v45(c)v143v5v4(d)v25v143v5v4求最短路径•求单源最短路径:Dijkstra(迪杰斯特拉)算法,时间复杂度O(n2)•求全局最短路径:Floyd算法,时间复杂度O(n3)•使用者两种算法的条件:要求必须是无环图Dijkstra算法(求顶点A到其他顶点的最短距离)算法思想如下:1.初始化源点A到其他顶点的距离,若其他顶点与源点A无直接相连的边,则认为源点A到该顶点的距离为无穷大(程序中使用int或longlong的最大值表示无穷大);2.选择当前距离源点A最近的顶点X(注意:顶点X必须未被选择过);3.以X点为参照,更新源点A到其他未被选择过的点M的距离若A-X-M小于A-M距离,则使用新距离替换原距离;若A-X-M大于等于A-M距离,则保持原距离不变;4.重复步骤2、3,直到选取完所有的点为止。求解过程:1.初始化源点A到B、C、D、E、F、G、H、I的路径长度2.从B、C、D、E、F、G、H、I中选择到源点A距离最小的顶点,该顶点为B3.以B为参照更新源点A到C、D、E、F、G、H、I的路径长度如果新路径长度小于原长度,则用新的长度作为A到该点的路径长度4.基于新的路径长度,重复步骤2、3。选择距离A点最近且未被选择过的点,直到选取完所有点Dijkstra算法(求A到其他顶点的最短距离,注:*表示无穷大)第1步源点ABCDEFGHI初始值参照B(A--B)343*6**4**BA---B---C路径长度为4(4*)A---B---D路径长度为*(*等于*)*A---B---E路径长度为*(*等于*)*A---B---F路径长度为*(*6)6A---B---G路径长度为*(*4)4A---B---H路径长度为10(10*)10A---B---I路径长度为*(*等于*)*Dijkstra算法(求A到其他顶点的最短距离,注:*表示无穷大)第2步求解过程:1.继续从C、D、E、F、G、H、I(需排除上一轮已被选择过的顶点B)中选择距源点A最近的点C2.以点C为参照更新源点A到D、E、F、G、H、I的路径长度如果新路径长度小于原路径长度,则用新的长度作为A到该点的路径长度3.基于新的路径长度,重复步骤1、2。源点ABCDEFGHI初始值参照B(A--B)343*6**4**B**6410*C参照C(A-(B)-C)34A--(B)--C---D路径长度为:4+8=12(12*)12A--(B)--C---E路径长度为:4+*=*(*==*)*A--(B)--C---F路径长度为:4+1=5(56)5A--(B)--C---G路径长度为:4+2=6(64)4A--(B)--C---H路径长度为:4+*=*(*10)10A--(B)--C---I路径长度为:4+9=13(13*)13Dijkstra算法(求A到其他顶点的最短距离,注:*表示无穷大)第3步源点ABCDEFGHI初始值参照B(A--B)343*6**4**B**6410*C参照C(A-(B)-C)3412*541013G参照G(A--G)3A--G--D路径长度为:4+*=*(*12)4继续从D、E、F、G、H、I中选择距源点A最近的点G(需排除前2轮已选择过的顶点B、C)参照G更新源点A到D、E、F、H、I的路径长度412A--G--E路径长度为:4+*=*(*==*)*A--G--F路径长度为:4+*=*(*5)5A--G--H路径长度为:4+4=8(810)8A--G--I路径长度为:4+*=*(*13)13Dijkstra算法(求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的路径长度源点ABCDEFGHI初始值参照B(A--B)343*6**4**B**6410*C参照C(A-(B)-C)3412*541013G参照G(A--G)34412*5813F12参照F(A-(B、C)-F)3445A-(B、C)-F--E路径长度为:5+*=*(*==*)*A-(B、C)-F--H路径长度为:5+2=7(78)7A-(B、C)-F--I路径长度为:5+*=*(*13)13Dijkstra算法(求A到其他顶点的最短距离,注:*表示无穷大)第5步A-(B、C、F)-H--D路径长度为:7+3=10(1012)继续从D、E、H、I中选择距源点A最近的点H(需排除前4轮已选择过的顶点B、C、F、G)参照H更新源点A到D、E、I的路径长度源点ABCDEFGHI初始值参照B(A--B)343*6**4**B**6410*C参照C(A-(B)-C)3412*541013G参照G(A--G)34412*5813F12参照F(A-(B、C)-F)3445*713H参照H(A-(B、C、F)-H)3445710A-(B、C、F)-H--E路径长度为:7+*=*(*==*)*A-(B、C、F)-H--I路径长度为:7+4=11(1113)11Dijkstra算法(求A到其他顶点的最短距离,注:*表示无穷大)第6步A-(B、C、F、H)-D--E路径长度为:10+5=15(15*)继续从D、E、I中选择距源点A最近的点D(需排除前5轮已选择过的顶点B、C、F、G、H)参照D更新源点A到E、I的路径长度源点ABCDEFGHI初始值参照B(A--B)343*6**4**B**6410*C参照C(A-(B)-C)3412*541013G参照G(A--G)34412*5813F12参照F(A-(B、C)-F)3445*713H参照H(A-(B、C、F)-H)3445710*11参照D(A-(B、C、F、H)-D)3445710D15A-(B、C、F、H)-D--I路径长度为:10+*=*(*11)11Dijkstra算法(求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)源点ABCDEFGHI初始值参照B(A--B)343*6**4**B**6410*C参照C(A-(B)-C)3412*541013G参照G(A--G)34412*5813F12参照F(A-(B、C)-F)3445*713H参照H(A-(B、C、F)-H)3445710*11参照D(A-(B、C、F、H)-D)3445710D151115参照I(A-(B、C、F、H)-I)344571011I2、参照I更新源点A到E的路径长度Dijkstra算法的求解思想•每次,都以已经求出的最短路径为基础,去求解到其他顶点的最短路径。•该过程与动态规划“由一个阶段的最优解,推出其他阶段的最优解类似”•因此Dijkstra运用了“动态规划”的求解思想。谢谢观赏!

1 / 28
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功