最小生成树与最短路径问题

HuJunfengHuJunfeng图——最小生成树与最短路径问题2009/05/14HuJunfengHuJunfeng2基于邻接表的图操作运算HuJunfengHuJunfeng3基于邻接表的图操作运算HuJunfengHuJunfeng4HuJunfengHuJunfeng5主要内容•生成树的概念（spanningtree）•Prim算法•Kruskal算法•最短路径问题•Dijkstra算法•Floyd算法HuJunfengHuJunfeng6生成树（支撑树）的概念GraphMatrixgraph={6,{{0,10,M,M,19,21},{10,0,5,M,M,11},{M,5,0,M,M,M},{M,M,M,0,18,14},{19,M,M,18,0,33},{21,11,M,14,33,0}}};012345子图+连通+无环HuJunfengHuJunfeng7无向图中无环的充要条件•检查每一个连通分枝•对于所有连通分枝：顶点数–边的数目=1可以采用周游算法。算法复杂度：n012345HuJunfengHuJunfeng8最小生成树Minimum-costSpanningTree•连通无向带权图——网络。•网络（带权图）的生成树中生成树各边的权值加起来称为生成树的权，把权值最小的生成树称为最小生成树。(简称为MST)。HuJunfengHuJunfeng9•G=(V，E)是一个网络，U是顶点集合V的一个真子集。•如果u∈U，v∈V-U，且边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边，则一定存在G的一棵最小生成树包括此边(u,v)。MST必包含连通图中任意两个顶点划分之间的最小权的边。（任意割集中的最小边）MST性质HuJunfengHuJunfeng10MST性质证明（反证法）uu´vv´UV-Uvv•边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边。•假设：存在G的一棵最小生成树不包括此边。HuJunfengHuJunfeng11Prim算法（找MST）prim算法的基本思想是∶①首先从集合V中任取一顶点(例如取顶点v0)放入集合U中这时U={v0}，TE=NULL②然后在所有一个顶点在集合U里，另一个顶点在集合V-U里的边中，找出权值最小的边(u,v)(u∈U，v∈V-U)，将边加入TE，并将顶点v加入集合U③重复上述操作直到U=V为止。这时TE中有n-1条边，T=(U，TE)就是G的一棵最小生成树HuJunfengHuJunfeng12最小生成树的构造•准备工作：①设图采用邻接矩阵表示法表示，用一对顶点的下标(在顶点表中的下标)表示一条边，定义如下∶②在构造最小生成树的过程中定义一个类型为Edge的数组mst∶Edgemst[n-1];其中n为网络中顶点的个数，算法结束时，mst中存放求出的最小生成树的n-1条边。typedefstruct{intstart_vex,stop_vex;/*边的起点和终点*/AdjTypeweight;/*边的权*/}Edge;HuJunfengHuJunfeng13例子：mst∶Edgemst[n-1];已知带权图G及其邻接矩阵如图所示请构造该图的最小生成树v010v121115v51933146v26v418v30331411213301819141806660511650102119100HuJunfengHuJunfeng14①n=6，只有顶点v0在最小生成树中。mst[5]={{0,1,10},{0,2,∞},{0,3,∞},{0,4,19},{0,5,21}}②在mst[0]到mst[4]中找出权值最小的边mst[0]，即(v0,v1)，将顶点v1及边(v0,v1)加入最小生成树。v010v121115v51933146v26v418v303314112133018191418066605116501021191001n-1HuJunfengHuJunfeng15①n=6，只有顶点v0在最小生成树中。mst[5]={{0,1,10},{0,2,∞},{0,3,∞},{0,4,19},{0,5,21}}②在mst[0]到mst[4]中找出权值最小的边mst[0]，即(v0,v1)，将顶点v1及边(v0,v1)加入最小生成树。③调整：mst[5]={{0,1,10},{1,2,5},{1,3,6},{0,4,19},{1,5,11}}v010v121115v51933146v26v418v303314112133018191418066605116501021191002n-2比较HuJunfengHuJunfeng16mst[5]={{0,1,10},{1,2,5},{1,3,6},{3,4,18},{1,5,11}}mst[5]={{0,1,10},{1,2,5},{1,3,6},{3,4,18},{1,5,11}}03314112133018191418066605116501021191003n-3v010v121115v51933146v26v418v3HuJunfengHuJunfeng17mst[5]={{0,1,10},{1,2,5},{1,3,6},{1,5,11},{3,4,18}}v010v121115v51933146v26v418v3HuJunfengHuJunfeng18调整为成新边HuJunfengHuJunfeng19Prim算法时间复杂度•Prim算法的时间主要花费在选择最小生成树的n-1条边上。外循环执行n-1次，内循环两个，时间耗费为：•整个算法的时间复杂度为O(n2)20221202)1(2))1()1((ninijnijninijOOOHuJunfengHuJunfeng20贪心算法一般思路•初态（起点）•候选对象集合•贪心选择算法（按当前状态）•可行评估函数•目标函数HuJunfengHuJunfeng21Kruskal算法•设G=(V，E)是网络，最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，φ)，T中每个顶点自成为一个连通分量。•将集合E中的边按权递增顺序排列，从小到大依次选择顶点分别在两个不同连通分量中的边加入图T，则原来的两个连通分量由于该边的连接而成为一个连通分量。•依次类推，直到T中所有顶点都在同一个连通分量上为止，该连通分量就是G的一棵最小生成树。HuJunfengHuJunfeng22例题∶用Kruskal方法构造图的最小生成树•集合E中的边按权递增顺序排列为∶(v1,v25),(v1,v36),(v2,v36),(v0,v110),(v1,v511),(v3,v514),(v3,v418),(v0,v419),(v0,v521),(v4,v533)v010v121115v51933146v26v418v3HuJunfengHuJunfeng23①初始时，T为只有6个顶点的非连通图。②边(v1,v2)的两个顶点v1，v2分别属于两个连通分量，将边(v1,v2)加入T。③同理，将边(v1,v3)加入T。④由于边(v2,v3)的两个顶点v2，v3属于同一个连通分量，因此，舍去这条边。⑤同理将边(v0,v1)、(v1,v5)加入T，边(v3,v5)舍去，边(v3,v4)加入T。这时T中含的边数为5条，成为一个连通分量，T就是G的一棵最小生成树。HuJunfengHuJunfeng24HuJunfengHuJunfeng25算法框架•T=(V,φ)while(T中所含边数n-1){从E中选取当前最短边(u,v)；从E中删去边(u,v)；if((u,v)加入T中后不产生回路)将边(u,v)加入T中；}HuJunfengHuJunfeng26最短路径问题•如果图中从一个顶点可以到达另一个顶点，则称这两个顶点间存在一条路径。从一个顶点到另一个顶点间可能存在多条路径，而每条路径上经过的边数并不一定相同。•如果图是一个带权图，则路径长度为路径上各边的权值的总和，两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径，其路径长度称为最短路径长度。HuJunfengHuJunfeng27Dijkstra算法——SingleSource/AllDestinations•Dijkstra算法求解从顶点v0出发到其它各顶点最短路径。01234567SanFranciscoDenverChicagoBostonNewYorkMiamiNewOrleansLosAngeles3001000800120015001400100090017001000250HuJunfengHuJunfeng28基本思想•设置一个集合U，存放已求出最短路径的顶点，V-U是尚未确定最短路径的顶点集合。•每个顶点对应一个距离值，集合U中顶点的距离值是从顶点v0到该顶点的最短路径长度；•集合V-U中顶点的距离值是从顶点v0到该顶点的只包括集合U中顶点为中间顶点的最短路径长度。HuJunfengHuJunfeng29初始状态：•集合U中只有顶点v0，顶点v0对应的距离值为0，集合V-U中顶点vi的距离值为边(v0,vi)(i=1,2,…,n-1)的权，如果v0和vi间无边直接相连，则vi的距离值为∞。HuJunfengHuJunfeng30处理框架：（1）在集合V-U中选择距离值最小的顶点vmin加入集合U；（2）对集合V-U中各顶点的距离值进行修正：如果加入顶点vmin为中间顶点后，使v0到vi的距离值比原来的距离值更小，则修改vi的距离值。（3）重复（1）（2）操作，直到从v0出发可以到达的所有顶点都在集合U中为止。HuJunfengHuJunfeng31存储结构•图采用邻接矩阵表示法，其中对角线元素初值均取0。•算法中，将放入集合Ｕ中结点对应的关系矩阵中对角线元素值修改为1；•设置一个数组dist，dist[ｉ]用于存放v0到顶点vｉ的最短路径及其最短路径长度（计算过程中为距离值）∶ypedefstruct{AdjTypelength;/*最短路径长度*/intprevex;/*从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点*/}Path;Path*dist;HuJunfengHuJunfeng32修正距离值的方法如果加入顶点vmin为中间顶点后dist[i].lengthdist[min].length+G.arcs[min][i]则将顶点vi的距离值改为dist[min].length+G.arcs[min][i]并修改路径上vi的前趋顶点：dist[i].prevex=minHuJunfengHuJunfeng33例子：初始状态V={v0}•结果dist[n]为{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}HuJunfengHuJunfeng34②．在集合V-U中找出距离值最小的顶点v2，将顶点v2加入集合U中。原：dist[n]为{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}后：dist[n]为{{0,0},{50,0},{10,0},{25,2},{45,0},{MAX,-1}}HuJunfengHuJunfeng35（接）同理在集合V-U中找出当前距离值最小的顶点v3，并调整集合V-U中顶点的距离值。原：dist[n]为{{0,0},{50,0},{10,0},{25,2},{45,0},{MAX,-1}}后：dist[n]为{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}HuJunfengHuJunfeng36最后：•在集合V-U中