图的基本概念图的存储结构图的遍历最小生成树最短路径

图的基本概念图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径最短路径(ShortestPath)最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。问题解法单源最短路径—Dijkstra算法任意顶点对之间的最短路径—Floyd算法单源最短路径问题问题的提出：给定一个带权有向图G与源点v，求从v到G中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。举例说明Dijkstra逐步求解的过程源点终点最短路径路径长度v0v1(v0,v1)10v2—(v0,v1,v2)(v0,v3,v2)—6050v3(v0,v3)30v4(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)1009060算法的基本思想设置并逐步扩充一个集合S，存放已求出的最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，为了直观起见，我们设想S中顶点均被涂成红色，V-S中的顶点均被涂成蓝色。算法初始化时，红点集中仅有一个源点，以后每一步都是按最短路径长度递增的顺序，逐个地把蓝点集中的顶点涂成红色后，加入到红点集中。算法粗框：while(S中的红点数n)在当前蓝点集中选择一个最短路径长度最短的蓝点扩充到蓝点集中；那么，如何在蓝点集中选择一个最短路径长度最短的蓝点呢？注意：这种蓝点所对应的最短路径上，除终点外，其余顶点都是红点。为此，对于图中每一个顶点i，都必须记住从v到i、且中间只经过红点的最短路径的长度，并将此长度记作i的距离值。开始时，红点集只有一个源点v，初始蓝点集中的蓝点j的距离值D[j]均为有向边v,j上的权值。用数组D(n)来存放n个顶点的距离值。若当前蓝点集中具有最小距离值的蓝点是k，则其距离值D(k)是k的最短路径长度，并且k是蓝点集中最短路径长度最短的顶点。证明１：（距离值D(k)是k的最短路径长度）若D(k)不是k的最短路径长度，则必存在另外一条从源点v到k的路径P，其长度小于D(k)。由距离值的定义可知，路径P上必然包含一个或多个蓝点作为中间点。假设从源点沿P向前第一次碰到的蓝点是x，则P上从源点v到x的这一段路径的长度，显然不小于x的距离值D(x)。而P上从x到终点k所经过的边上，其权值均为非负实数，所以D(x)=P的长度。又因为P的长度D(k)(这是假设前提)，于是有下述不等式：D(x)=P的长度D(k)由此可知：D(x)D(k)，这与k是蓝点集中距离值最小的蓝点产生矛盾。所以D(k)是k的最短路径长度。蓝点k蓝点x红点集S源点v证明２：（k是蓝点集中最短路径长度最短的顶点）设i是蓝点集中任何一个异于k的顶点，若i的最短路径只经过红点，则该最短路径长度是i的距离值D(i),因为D(k)是当前蓝点集距离值最小的顶点，所以D(i)=D(k)。若i的最短路径P包含其它蓝点作为中间点，设P上第一个蓝点是j，则P上从v到j的路径长度就是j的距离值D(j)。显然，D(j)=D(k)，而P的长度=D(j)+j到i的长度，因为j到i的长度为非负实数，所以P的长度=D(k)。由此可知蓝点集中任意顶点i的最短路径长度都不会小于k的最短路径长度D(k)。扩充红点集的方法：每一步只要在当前蓝点集中选择一个具有最小的距离值的蓝点k扩充到红点集合中，k被涂成红色之后，剩余的蓝点的距离值可能由于增加了新红点k而发生变化（即减少）。因此必须调整当前蓝点集中各蓝点的距离值。算法框架：S={v};置初始蓝点集中各蓝点的距离值；while(S中红点数n){在当前蓝点集中选择距离值最小的顶点k；S=S+{k};/*将k涂成红色加入红点集*/调整剩余蓝点的距离值；}如何调整剩余蓝点的距离值呢？若新红点k加入红点集S后，使得某个蓝点j的距离值D(j)减少，则必定是由于存在一条从源点v途径新红点k最终到达蓝点j且中间只经过红点的、新的最短路径Pvkj，它的长度小于从源点v到达j且中间只经过老红点（即步包含k）的原最短路径Pvj的长度D(j)。由于Pvkj是一条中间只经过红点的最短路径，所以，它的前一段从v到k的路径必定是k的最短路径，其长度为D(k)；它的后一段从k到j的路径Pkj只可能有两种情形：其一是由k经过边k,j直达蓝点j；其二是从k出发再经过S中若干老红点后到达j。用反正法证明后一种情形是不可能的。假设从源点v出发，经过红点k、老红点x，最后到达蓝点j的新最短路径Pvkxj的长度小于原D(j)。因为x比k先加入红点集S，故D(x)=D(k)，又因为权值非负，所以从v到x的路径Pvx的长度不大于从v经k到x的路径Pvkx的长度，即length(Pvk)=D(x)=D(k)+length(Pkx)=length(Pvkx)因此从v经x到j的路径长度:length(Pvxj)=length(Pvk)+length(Pxj)不大于从v经k、x到j的新路径长度length(Pvkxj)=length(Pvkx)+length(Pxj)又因为Pvxj中间只经过老红点，所以Pvxj的长度不大于D(j)的值，由此可得：D(j)=length(Pvxj)=length(Pvkxj)这与新路径Pvkxj的长度小于原D(j)值的假设相矛盾！因此，使得D(j)值减小的新路径比必是先经过老红点到达k，然后经过边k,j直达蓝点j的，它得长度是D(k)+边k,j上的权。由此得到调整距离值的方法：当顶点k从蓝点集转移到红点集时，对蓝点集扫描检查，若某蓝点j的原距离值D(j)大于新路径的长度D(k)+边k,j上的权，则将D(j)修改成此长度值。为了同时得到路径，设置一个路径向量P[n],其中P[i]表示从源点到达i点的最短路径上该点的前驱顶点。蓝点j蓝点k红点集S源点vx循环红点集k+1D[0]…D[4]P[]…P[4]初始化１２３４｛4｝{4,3}{4,3,5}{4,3,5,1}{4,3,5,1,2}-3512maxmax20060maxmax20030maxmax20030maxmax20030maxmax200300040400403004030040300403１２５３４501030102060100max1max2203-404305-3-4１２５３４10301020floatD[n];intP[n],S[n];DIJKSTRA(floatC[][n],intv){inti,j,k,v1,pre;intmin,max=60,inf=80;v1=v-1;for(i=0;in;i++){D[i]=C[v1][i];if(D[i]!=max)P[i]=v;elseP[i]=0;}for(i=0;in;i++)S[i]=0;S[v1]=1;D[v1]=0;for(i=0;in-1;i++){min=inf;for(j=0;jn;j++)if((!S[j])&&(D[j]min)){min=D[j];k=j;}S[k]=1;for(j=0;jn;j+=)if((!S[j])&&(D[j]D[k]+C[k][j])){D[j]=D[k]+C[k][j];P[j]=k+1;}}for(i=0;in;i++){printf(“%f\n%d”,D[i],i+1);pre=p[i];while(pre!=0){printf(“--%d”,pre);pre=P[pre-1];}}}算法说明对于顶点i和j：1、首先，考虑从i到j是否有以顶点1为中间点的路径，：i，1，j，即考虑图中是否有边i,1和1,j，若有，则新路径i，1，j的长度是C[i][1]+C[1][j]，比较路径i，j和i，1，j，的长度，并以较短者为当前所求得的最短路径，。该路径是中间点序号不大于1的最短路径。所有顶点对之间的最短路径2、其次，考虑从i到j是否包含顶点2为中间点的路径：i，...，2，...，j，若没有，则从i到j的最短路径仍然是第一步中求出的，即从i到j的中间点序号不大于1的最短路径；若有，则i，...，2，...，j可分解成两条路径i，...，2和2，...，j，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径相加就得到路径i，...，2，...，j的长度，将该长度与前一次求出的从i到j的中间点序号不大于1的最短路径长度比较，取其较短者作为当前求得的从i到j的中间点序号不大于2的最短路径。3、然后，再选择顶点3加入当前求得的从i到j中间点序号不大于2的最短路径中，按上述步骤进行比较，从未加入顶点3作中间点的最短路径和加入顶点3作中间点的新路径中选取较小者，作为当前求得的从i到j的中间点序号不大于3的最短路径。依次类推，直到考虑了顶点n加入当前从i到j的最短路径后，选出从i到j的中间点序号不大于n的最短路径为止。由于图中顶点序号不大于n，所以从i到j的中间点序号不大于n的最短路径，已考虑了所有顶点作为中间点的可能性。因而它必是从i到j的最短路径。算法的基本思想就是：从初始的邻接矩阵A0开始，递推地生成矩阵序列A1，A2，...，An]][[]][[0jiCjiA]}][[]][[],][[min{]][[1jkAkiAjiAjiAkkkk显然，A中记录了所有顶点对之间的最短路径长度。若要求得到最短路径本身，还必须设置一个路径矩阵P[n][n]，在第k次迭代中求得的path[i][j]，是从i到j的中间点序号不大于k的最短路径上顶点i的后继顶点。算法结束时，由path[i][j]的值就可以得到从i到j的最短路径上的各个顶点。Floyd算法intpath[n][n];FLOYD(floatA[][n],floatC[][n]){inti,j,k,next;intmax=160;for(i=0,in,i++)for(j=0;jn;j++){if(C[i][j]!=max)path[i][j]=j;elsepath[i][j]=0;A[i][j]=C[i][j];}for(k=0;kn;k++)for(i=0;in;i++)for(j=0;jn;j++)if(a[i][j](A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];path[i][j]=path[i][k];}for(i=0;in;i++)for(j=0;jn;j++){printf(“%f”,A[i][j]);next=path[i][j];if(next==0)printf(“%dto%dnopath.\n”,i+1;j+1);else{printf(“%d”,i+1);while(next!=j){printf(“--%d”,next+1);next=path[next][j];}printf(“--%d”,j+1);}}}１２５３４50103010206010006002010050010030100A00600201005001003060100A2030020100605001003060100A3030020100605001003050100A4拓扑排序计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的