图的存储与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运用了“动态规划”的求解思想。谢谢观赏!