数据结构-拓扑排序和最短路径

最短路径问题拓扑排序某个源点到其余各点的最短路径每一对顶点之间的最短路径小结和作业拓扑排序一、定义由集合上的一个偏序关系得到集合的全序关系的操作偏序：自反的、反对称的、传递的全序：R是集合X上的偏序，对于集合X中的任何元素x,y，如果都有xRy或者yRx,则称R是全序关系拓扑排序BDACBDAC•偏序就是集合中的部分成员可以比较。•全序是集合中的任何成员之间都可以比较。偏序全序拓扑排序按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列拓扑排序用顶点表示活动，弧表示活动间的优先关系的有向图。AOV网（ActivityOnVertexNetWork）AOV网中不应该出现有向环：如果存在环，则某项活动以自己为先决条件，拓扑排序BDAC可求得拓扑有序序列：ABCD或ACBDBDAC不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}拓扑排序拓扑排序---方法11、从有向图中选取一个没有前驱的顶点，并输出之;2、从有向图中删去此顶点以及所有以它为尾的弧;3、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。拓扑排序---方法1acgbdhfebhacdgfe拓扑序列：在算法中需要用定量的描述替代定性的概念没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减1拓扑排序---方法1StatusToplogicalSort(ALGraghG){FindInDegree(G,indegree);InitStack(S);for(i=0;iG.vexnum;i++){if(!indegree[i])push(S,i);}count=0;//对输出顶点计数while(!EmptyStack(S)){…………}//whileif(countG.vexnum)returnERROR;elsereturnOK;}拓扑排序---算法StatusToplogicalSort(ALGraghG){………………while(!EmptyStack(S)){Pop(S,v);++count;printf(v);for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){--indegree(w);//弧头顶点的入度减1if(!indegree[w])Push(S,w);}//for}//while………………}拓扑排序---算法总的时间复杂度：O(n+e)算法分析：拓扑排序---算法拓扑排序---方法2acgbdhfebhacdgfe拓扑序列：对有向无环图利用深度优先搜索进行拓扑排序。拓扑排序---方法2acgbdhfebhacdgfe此图的一个拓扑序列为：acgbdhfe退出DFS函数顺序：efgdcahb拓扑排序---方法2最先退出DFS函数的顶点是出度为零的顶点，为拓扑排序序列中最后一个顶点。因此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑排序序列。结论：拓扑排序---方法2voidDFS-ToplogicalSort(GraphG,intv){//如何确定vfor(v=0;vG.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化InitStack(S);//存放顶点，按照出DFS的次序for(v=0;vG.vexnum;++v){if(!visited[v])DFS-T(G,v);//对尚未访问的顶点调用DFS}while(!Empty(S)){//输出拓扑排序的结果Pop(S,v);printf(“%d”,v)}}拓扑排序---方法2voidDFS-T(GraphG,intv){//从顶点v出发，深度优先搜索遍历连通图Gvisited[v]=TRUE;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)){if(!visited[w])DFS-T(G,w);}//对v的尚未访问的邻接顶点w递归调用DFS-TPush(S,v);//顶点v的DFS函数执行完毕}//DFS-T拓扑排序---练习acgbdhfe写出下图的所有的拓扑序列单源点的最短路径V01010V1V2V5V4V32030给定带权有向图G和V0，求从V0到其余各顶点的最短路径。Dijkstra算法1、按照路径长度递增的次序产生最短路径源点v1…v2将最短路径的终点命名为V1，次之的终点命名为V2，……Dijkstra算法S={V0}S={V0,V1}S={V0,V1,V2}…….2、用集合S记录下已经求出的顶点Dijkstra算法3、用数组D记录V0到S中每个顶点的最短路径的长度S={V0,V1,V2,…,Vm}D[i]是V0到Vi的长度0=i=m源点v1…v21、长度最短的路径V01010V1V2V5V4V32030Dijkstra算法2、假设已经求出了V0到V1至Vk-1的最短路径即：S={V0,V1,…,Vk-1}3、求下一条最短路径，终点为Vk（不在S中）V0--Vk则该路径上的顶点一定都在S中Dijkstra算法用反证法：假设存在WSV0--W--Vk(V0--W中的顶点都在S中）那么，我们就会选择W作为Vk，而不会选择Vk，矛盾。Dijkstra算法因为V0--W比V0--Vk短路径的形式一定为：V0-Vi1-Vi2…-Vip-VkDijkstra算法Vi1，Vi2……，Vip∈SV0到Vk的最短路径是V0到Vip的最短路径+Vip到Vk的边如何找到Vk?Dijkstra算法min(D[i]+dur(i,k))i=0,1,…k-1VkSV01010V1V2V5V4V32030S={V0}D[0]=0S={V0,V2}D[1]=10S={V0,V2,V4}D[2]=30S={V0,V2,V4,V3}D[3]=50S={V0,V2,V4,V3,V5}D[4]=60V2V5V4V3Dijkstra算法为了减少计算量，改变一下计算次序初始时：D[k]=源点到顶点k的弧上的权值当S=S∪{Vj}，修改D[K]=min(D[k],D[Vj]+Vj,K)Dijkstra算法1）设置初始值：2）从D中选择一个最小值，假设为D[k]，要求Vk不在S中3）修改不在S中的每个顶点u的最短路径值若D[k]+G.arcs[k][u]D[u]则D[u]=D[k]+G.arcs[k][u]INFINITYkvarcsGkD]][0[.][V0和k之间存在弧V0和k之间不存在弧Dijkstra算法S={V0}4）重复2，3，直到所有的顶点都在S中如何保存V0到V的路径？1、保存V0到V的路径上的顶点（即：不保存边和顶点之间的顺序）2、存储结构：n×n的矩阵pDijkstra算法3、矩阵的第V行表示V0到V的路径上顶点如果顶点W在路径上，则p[v][w]=TRUE否则，p[v][w]=FALSE初始：如果V与顶点V0邻接，则p[v][V0]=TRUE，其它数矩阵元素的值都是FALSE。当从V0到V的路径是经过V0到W的路径，然后，通过边W,V到达V，则p[v]=p[w]，p[v][v]=TRUEDijkstra算法Dijkstra算法V01010V1V2V5V4V32030FFFFFFV0V1V2V3V4V5V0V1V2V3V4V5FFFFFFTFTFFFFFFFFFTFFFTFTFFFFT选取V2后，V0到V3的路径经过V2P[V3]=P[V2]P[V3][V3]=TRUETFTFFFTFTTFFDijkstra算法实现图：带权的邻接矩阵路径：矩阵距离：数组DS：数组final[]，如果final[v]=TRUE，则v在S中voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortestPathTable&D){for(v=0;vG.vexnum;++v){final[v]=FALSE;//S中的顶点D[v]=G.arcs[v0][v];//v0到v的路径的长度for(w=0;wG.vexnum;++w)p[v][w]=FALSE;if(D[v]INFINITY){//V0的邻接点p[v][v0]=TRUE;p[v][v]=TRUE;}//if}//forfinal[v0]=TRUE;…………}Dijkstra算法实现voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortestPathTable&D){//主循环，每次求得v0到某个顶点v的最短路径，//并将v加到S集中for(i=1;iG.vexnum;++i){min=INFINITY;//找余下顶点中的最短路径for(w=0;wG.vexnum;++w){if(!final[w])if(D[w]min){v=w;min=D[w];}final[v]=TRUE;//v入选，即v0到v的路径最短…………}}Dijkstra算法实现voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortestPathTable&D){for(w=0;wG.vexnum;++w){if(!final[w]&&(min+G.arcs[v][w]D[w])){D[w]=min+G.arcs[v][w];//修改距离p[w]=p[v];//修改路径p[w][w]=TRUE;}//if}//for}//voidDijkstra算法实现abcdefg15210765910444终点bcdefgD路径15ab2ac10ad29ace6acf6169101414acfgadg课堂练习Dijkstra算法讨论2、权值要为正数，否则，得不到正确结果1、算法的总的时间复杂度：O(n2)3、当权值出现负数时，要使用Bellman-Flord算法Dijkstra算法讨论都是从一个顶点开始都有一个距离数组D都有一个顶点是否已经被选取的标志4、和Prim算法有相似和不同的地方abcdegf195141827168213127abegf14d8c351621Prim算法产生的最小生成树67Dijkstra算法讨论abcdegf195141827168213127abegf14d8c51821Dijkstra算法产生的支撑树8519Dijkstra算法讨论每一对顶点之间的最短路径v0v2v1326411cab问题：给定一个图G，求出G中任意两个顶点之间的最短路径（距离和经过的顶点）解决方法：对图中的每个结点V，以V为源点，调用Dijkstra算法时间复杂度为O(n3)显然，顶点vi和vj之间的最短路径通过了n个顶点的某些顶点。Floyd算法首先对顶点进行编号，n个顶点对应1……n个整数，分别叫做V1，V2,……，Vn弗洛伊德算法的基本思想是动态规划Floyd算法1、求出顶点Vi和Vj不经过任何顶点的最短路径，路径的长度就是二者之间边的权重，表示为：)0(ijP2、当求出后，即Vi到Vj经过V1到Vk-1中的某些顶点的最短路径。)1-k(ijP则：Vi到Vj的中间经过V1到Vk中某些顶点的最短路径：)k(ijPFloyd算法)k(ijP=)1-k(ijP(1)ViVjVk1……k-1Floyd算法)k(ijP=)1-k(ikP+)1-k(kjP(2)ViVjVk1……k-11……k-1Floyd算法综合(1)和(2)，有：=min(,))k(ijP)1-k(ikP+)1-k(kjP)1-k(ijP3、当k=n时，即就是Vi和Vj之间的最短路径)n(ijPFloyd算法1.定义一个n阶方阵D(-1)，表示初始时，任意两个顶点(i,j)之间的距离D(-1)[i][j]=G.arcs[i][j]由D(k-1)生成新的矩阵D(k),表示任意2个顶点之间最短路径的长度，中间经过的顶点的编号小于K。D(k)=min(D(k-1)[i][j],D