算法设计与分析-第2版-第9章-图算法设计

第9章图算法设计9.1求图的最小生成树9.2求图的最短路径9.3求解旅行商问题9.4网络流9.1.1最小生成树的概念一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的n-1条边。对于一个带权（假定每条边上的权均为大于零的数）连通无向图G中的不同生成树，其每棵树的所有边上的权值之和也可能不同；图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。9.1求图的最小生成树9.1.2普里姆算法构造最小生成树1.普里姆算法构造最小生成树的过程

普里姆（Prim）算法是一种构造性算法。假设G=(V，E)是一个具有n个顶点的带权连通无向图，T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点v出发的最小生成树T的步骤如下：

（1）初始化U={v}。以v到其他顶点的所有边为候选边；

（2）重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：

①以顶点集U和顶点集V-U之间的所有边（称为割集(U，V-U)）作为候选边，从中挑选权值最小的边（称为轻边）加入TE，设该边在V-U中的顶点是k，将k加入U中；②考察当前V-U中的所有顶点j，修改候选边：若(k，j)的权值小于原来和顶点j关联的候选边，则用(k，j)取代后者作为候选边。504136218676534250413621663422.普里姆算法设计为了便于在集合U和V-U之间选择权最小的边，建立了两个数组closest和lowcost，它们记录从U到V-U具有最小权值的边，对于某个j∈V-U，closest[j]存储该边依附的在U中的顶点编号，lowcost[j]存储该边的权值。closest[j]vkjlowcost[j]V-U={j|lowcost[j]≠0U={i|lowcost[i]=0增量过程（V-U的顶点一个一个添加到U中）：5041362186765342UV-U1：lowcost[1]=6，closest[1]=02：lowcost[2]=∞，closest[2]=-13：lowcost[3]=∞，closest[3]=-16：lowcost[6]=∞，closest[6]=-14：lowcost[4]=8，closest[4]=5lowcost[1]最小，将k=1添加到U中5041362186765342UV-U仅修改V-U中顶点j：g.edges[k][j]<lowcost[j]调整 lowcost[j]=g.edges[k][j] closest[j]=kvoidPrim(MGraphg,intv) //Prim算法{intlowcost[MAXV];intmincost;intclosest[MAXV],i,j,k;for(j=0;j<g.n;j++) //给初始化lowcost和closest数组{ lowcost[j]=g.edges[v][j]; closest[j]=v;}

Prim(g，v)算法利用上述过程构造最小生成树，其中参数g为带权邻接矩阵，v为起始顶点的编号。for(i=1;i<g.n;i++) //找出(n-1)个顶点{ mincost=INF;

for(j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k if(lowcost[j]!=0&&lowcost[j]<mincost) {mincost=lowcost[j]; k=j; //k记录最近顶点的编号 }

printf("边(%d,%d)权为:%d\n",closest[k],k,mincost); lowcost[k]=0; //标记k已经加入U for(j=0;j<g.n;j++) //修改数组lowcost和closest if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j]) { lowcost[j]=g.edges[k][j]; closest[j]=k; }}}

Prim()算法中有两重for循环，所以时间复杂度为O(n2)，其中n为图的顶点个数。3.普里姆算法的正确性证明

普里姆算法是一种贪心算法。对于带权连通无向图G=(V，E)，采用通过对算法步骤的归纳来证明普里姆算法的正确性。

定理9.1对于任意正整数k<n，存在一棵最小生成树T包含Prim算法前k步选择的边。

证明：

（1）k=1时，用反证法证明存在一棵最小生成树T包含e=(0，i)，其中(0，i)是所有关联顶点0的边中权最小的。

令T为一棵最小生成树，假如T不包含(0，i)，那么根据命题9.1，T∪{(0，i)}含有一个回路，设这个回路中关联顶点0的边是(0，j)，

令：T'=(T-{(0，j)})∪{(0，i)}则T'也是一棵生成树，并且所有边权值和更小（除非(0，i)与(0，j)的权相同），与T为一棵最小生成树矛盾。

（2）假设算法进行了k-1步，生成树的边为e1，e2，…，ek-1，这些边的k个端点构成集合U，并且存在G的一棵最小生成树T包含这些边。

（3）算法第k步选择了顶点ik，则ik到U中顶点的边的权值最小，设这条边为ek=(ik，il)。假设最小生成树T不含有边ek，将ek添加到T中形成一个回路，如下图所示：ilikekUV-Uxye'

这个回路一定有连接U与V-U中顶点的边e'，用ek替换e'得到树T'，即：T'=(T-{e'})∪{ek}则T'也是一棵生成树，包含边e1，e2，…，ek-1，ek，并且T'所有边权值和更小（除非e'与ek的权相同），与T为一棵最小生成树矛盾。定理即证。

当k=n时，U包含G中所有顶点，由普里姆算法构造的T=（U，TE）就是G的最小生成树。ilikekUV-Uxye'9.3.3克鲁斯卡尔算法1.克鲁斯卡尔算法构造最小生成树的过程克鲁斯卡尔（Kruskal）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V，E)是一个具有n个顶点e条边的带权连通无向图，T=(U，TE)是G的最小生成树，则构造最小生成树的步骤如下：①置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个分量）。②将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE；否则舍弃，直到TE中包含n-1条边为止。504136218676534250413621663422.克鲁斯卡尔算法设计实现克鲁斯卡尔算法的关键是如何判断选取的边是否与生成树中已有的边形成回路，这可以通过并查集来解决。

对于一个数据序列和一个等价关系，并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并等运算，同一集合中的元素满足等价关系。当给出两个元素满足等价关系构成一个无序对(a，b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。

在这种数据结构中，n个不同的元素被分为若干组，每组是一个集合，这种集合叫做分离集合。可以采用有根树来表示集合，树中的每个结点包含集合的一个元素，每棵树表示一个集合。多个集合形成一个森林，以每棵树的根结点编号唯一标识该集合，并且根结点的父结点指向其自身，树上的其他结点都用一个父指针表示它的附属关系。1234（1,3）1234（2,3）1234采用顺序方法即采用一个数组t来存储森林，其中结点的类型定义如下：typedefstructnode{intdata; //结点对应顶点编号

intrank; //结点对应秩

intparent; //结点对应双亲下标}UFSTree; //并查集树的结点类型并查集的基本运算算法如下：voidMAKE_SET(UFSTreet[],intn) //初始化并查集树{for(inti=0;i<n;i++) //顶点编号为0～(n-1){t[i].rank=0; //秩初始化为0t[i].parent=i; //双亲初始化指向自已}}intFIND_SET(UFSTreet[],intx) //在x所在子树中查找集合的编号{if(x!=t[x].parent) //若双亲不是自已return(FIND_SET(t,t[x].parent)); //递归在双亲中找xelsereturn(x); //若双亲是自已,返回x}voidUNION(UFSTreet[],intx,inty) //将x和y所在的子树合并{x=FIND_SET(t,x);y=FIND_SET(t,y);if(t[x].rank>t[y].rank) //x结点的秩大于y结点的秩 t[y].parent=x; //将x结点作为y的双亲结点else //y结点的秩大于等于x结点的秩{t[x].parent=y; //将y结点作为x的双亲结点if(t[x].rank==t[y].rank) //x和y结点的秩相同t[y].rank++; //y结点的秩增1}}对于n元素构成的分离集合树，其高度最高为log2n，所以FIND_SET(t，x)和UNION(t，x，y)算法的时间复杂度均为O(log2n)。用一个数组E[]存放图G中的所有边，要求它们是按权值从小到大的顺序排列的，为此先从图G的邻接矩阵中获取所有边集E，再采用推排序法对边集E按权值递增排序。

数组E的元素类型定义如下：typedefstruct{intu; //边的起始顶点

intv; //边的终止顶点

intw; //边的权值}Edge;对应的克鲁斯卡尔算法如下：voidKruskal(MGraphg) //Kruskal算法{inti,j,k,u1,v1,sn1,sn2;UFSTreet[MaxSize];EdgeE[MaxSize];k=0;for(i=0;i<g.n;i++) //由g下三角部分产生的边集Efor(j=0;j<i;j++) if(g.edges[i][j]!=0&&g.edges[i][j]!=INF) {E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j]; k++; }sort(E,E+k);

//调用STL的sort()算法按w递增排序MAKE_SET(t,g.n); //初始化并查集树tk=1; //k表示当前构造生成树的第几条边,初值为1j=0; //E中边的下标,初值为0while(k<g.n) //生成的边数小于n时循环{u1=E[j].u;v1=E[j].v; //取一条边的头尾顶点编号u1和v2sn1=FIND_SET(t,u1);sn2=FIND_SET(t,v1); //分别得到两个顶点所属的集合编号if(sn1!=sn2)

//添加该边不会构成回路,将其作为最小生成树的一条边输出{printf("(%d,%d):%d\n",u1,v1,E[j].w);k++; //生成边数增1UNION(t,u1,v1); //将u1和v1两个顶点合并}j++; //扫描下一条边}}上述克鲁斯卡尔算法构造最小生成树的时间复杂度为O(elog2e)。3.克鲁斯卡尔算法的正确性证明

克鲁斯卡尔算法也是一种贪心算法。对于带权连通无向图G=(V，E)，采用通过对算法产生T=(V，TE)的边数k的归纳步骤来证明克鲁斯卡尔算法的正确性。

定理9.2克鲁斯卡尔算法可以找到一棵最小生成树。

证明：

（1）k=1时，首先T中没有任何边，设e1是G中权最小的边，加入e1不会产生任何回路。显然是正确的。

（2）假设算法进行了k-1步产生k-1条边，即e1，e2，…，ek-1，对应的边集合为TE1，产生的T1=(V1，TE1)是最小生成树T的子树（V1为TE1中的顶点集）。

（3）算法第k步选择了边e=(v，u)，设TE2=TE1∪{e}，TE2中的边把G中顶点分成两个或者两个以上的连通分量。

设S1是添加边e后包含顶点v的连通分量的顶点集，S2是添加边e后包含顶点u的连通分量的顶点集。

显然e是离开S的最短边之一（因为之前所有较短边都已经考察过，它们或者添加到T中，或者因为在同一个连通分量中而被丢弃）。

现要证明T2=(V2，TE2)也是最小生成树的子树（V2为TE2中的顶点集）。vueS1S2xye'

若最终的最小生成树T包含e=(v，u)，那么就不需要再进一步证明了。否则在T中S1和S2之间一定存在一条边e'=(x，y)（在后面添加的），现在再在S1和S2之间添加边e得必构成一个回路，如下图所示：

显然e'的权值大于或等于e的权值即cost(e')≥cost(e)，否则边e'应该在前面添加，这样由S1和S2加上e1构成的生成树的权值和大于等于T2的权值和，说明T不是最小生成树，与T是最小生成树的假设矛盾，从而证明T2是最小生成树的子树。当k=n-1时，由克鲁斯卡尔算法构造的T=(V，TE)就是G的最小生成树。对于带权图，考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或者最短距离。9.2求图的最短路径9.2.1狄克斯特拉算法1、狄克斯特拉算法的求解步骤基本思想是：设G=(V，E)是一个带权有向图，把图中顶点集合V分成两组：

第1组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径v，…，u，就将u加入到集合S中，直到全部顶点都加入到S中，算法就结束了）。

第2组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第2组的顶点加入S中。具体步骤：初始时，S只包含源点，即S={v}，顶点v到自已的距离为0。U包含除v外的其他顶点，v到U中顶点i的距离为边上的权（若v与i有边<v，i>）或∞（若i不是v的出边邻接点）。具体步骤：从U中选取一个顶点u，顶点v到顶点u的距离最小，然后把顶点u加入S中（该选定的距离就是v到u的最短路径长度）。以顶点u为新考虑的中间点，修改顶点v到U中各顶点的距离：若从源点v到顶点j（j∈U）经过顶点u的距离（图中为cvu+wuj）比原来不经过顶点u距离（图中为cvj）短，则修改从顶点v到顶点j的最短距离值（图中修改为cvu+wuj）。uvjcvucvjcuj两条路径中取最短者重复步骤②和③直到S包含所有的顶点。2、狄克斯特拉算法设计设置一个数组dist[0..n-1]，dist[i]用来保存从源点v到顶点i的目前最短路径长度，它的初值为<v，i>边上的权值，若顶点v到顶点i没有边，则权值定为∞。以后每考虑一个新的中间点时，dist[i]的值可能被修改而变小。

设置一个数组path[0..n-1]用于保存最短路径。path[j]保存当前最短路径中的前一个顶点的编号，它的初值为源点v的编号（顶点v到顶点j有边时）或-1（顶点v到顶点i无边时）。vuj…path[j]=uvoidDijkstra(MGraphg,intv) //Dijkstra算法{intdist[MAXV],path[MAXV];intS[MAXV];intmindis,i,j,u;for(i=0;i<g.n;i++){dist[i]=g.edges[v][i]; //距离初始化S[i]=0; //S[]置空if(g.edges[v][i]<INF) //路径初始化path[i]=v; //顶点v到顶点i有边时，置顶点i的前一个顶点为velsepath[i]=-1; //顶点v到顶点i没边时，置顶点i的前一个顶点为-1}S[v]=1;path[v]=0; //源点编号v放入s中for(i=0;i<g.n;i++) //循环直到所有顶点的最短路径都求出{mindis=INF; //mindis求最小路径长度for(j=0;j<g.n;j++) //选取不在s中且具有最小距离的顶点uif(S[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}S[u]=1;

//顶点u加入s中for(j=0;j<g.n;j++) //修改不在S中的顶点的距离if(S[j]==0)if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]){dist[j]=dist[u]+g.edges[u][j];path[j]=u;}}

//Dispath(g,dist,path,S,v); 输出最短路径}狄克斯特拉算法的时间复杂度为O(n2)，其中n为图中顶点个数。3、狄克斯特拉算法的正确性证明

狄克斯特拉算法也是一种贪心算法。证明Dijkstra算法可以找到图中从源点v到其他所有顶点的最短路径长度。用数学归纳法证明：

（1）如果顶点j在S中，则dist[i]给出了从源点到顶点i的最短路径长度。（2）如果顶点j不在S中，则dist[j]给出了从源点到顶点j的最短特殊路径长度，即该路径上的所有中间顶点都属于S。证明：初始时S中只有一个源点v，到其他顶点的路径就是从源点到相应顶点的边，显然（1）、（2）是成立的。假设向S中添加一个新顶点u之前，条件（1）、（2）都成立。（1）如果顶点j在S中，则dist[i]给出了从源点到顶点i的最短路径长度。（2）如果顶点j不在S中，则dist[j]给出了从源点到顶点j的最短特殊路径长度，即该路径上的所有中间顶点都属于S。

条件（1）的归纳步骤：对于每个在添加之前已经存在于S中的顶点u，不会有任何变化，条件（1）依然成立。

在顶点u加入到S之前，由假设可知dist[u]是源点到u的最短路径长度，还要验证从源点v到顶点u的最短路径没有经过任何不在S中的顶点。

假设存在这种情况，即沿着从源点v到顶点u的最短路径前进时，会遇到一个或多个不属于S的顶点（不含顶点u自已），设x是第一个这样的顶点，如下图所示。vxuS该路径的初始部分即从源点v到顶点x的部分是一条特殊路径，由假设的条件（2），dist[x]是源点v到顶点x的最短特殊路径长度，由于边非负，因此经过x到u的距离肯定不短于到x的距离。

又因为算法在x之前选择顶点u，因此dist[x]不小于dist[u]，这样经过x到u的距离就至少是dist[u]，所以经过x到u的最短路径不短于到u的最短特殊路径。

现在验证了当u加到S中时，dist[u]确定给出源点v到顶点u的最短路径长度，条件（1）是成立的。vxuS（1）如果顶点j在S中，则dist[i]给出了从源点到顶点i的最短路径长度。（2）如果顶点j不在S中，则dist[j]给出了从源点到顶点j的最短特殊路径长度，即该路径上的所有中间顶点都属于S。

条件（2）的归纳步骤：考虑不属于S且不同于u的一个顶点w，当u加到S中时，从源点v到w的最短特殊路径有两种可能：或者不会变化，或者现在经过顶点u（也可能经过S中的其他顶点）。

对于第2种情况，设x是到达w之前经过的S的最后一个顶点，因此这条路径的长度就是dist[x]+L(x，w)（L(x，w)为顶点x到顶点w的路径长度）。对于任意S中的顶点x（包括u），要计算dist[w]的值，就必须比较dist[w]原先的值和dist[x]+L(x，w)的大小。

因为算法明确地进行这种比较以计算新的dist[w]值，所以往S中加入新顶点u时，dist[w]仍然给出源点v到顶点w的最短特殊路径的长度，因此条件（2）也是成立的。9.4.2贝尔曼-福特算法1、贝尔曼-福特算法的求解思路贝尔曼-福特算法构造一个最短路径长度数组序列dist1[u]、dist2[u]、…、distn-1[u]。dist1[u]为源点v到终点u的只经过一条边的最短路径长度。dist2[u]为源点v最多经过两条边到达终点u最短路径长度。dist3[u]为源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度，…。distn-1[u]为源点v出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径长度。算法的最终目的是计算出distn-1[u]。设已经求出distk-1[u]（0≤k≤n-1），即从源点v最多经过不构成负权值回路的k-1条边到达终点u的最短路径长度，从图的邻接矩阵g中可以找到各个顶点i到达顶点u的距离g.edges[i][u]。

计算MIN{distk-1[i]+g.edges[i][u]}，可以得到从源点v绕过各个顶点最多经过不成负值回路的k条边到达终点u的最短路径的长度，比较distk-1[u]和MIN{distk-1[i]+g.edges[i][u]}，取较小者作为distk[u]的值。所以得到以下递推关系式：dist1[u]=g.edges[v][u]distk[u]=MIN{distk-1[u]，MIN{distk-1[i]+g.edges[i][u]}}，

i=0，1，…，n-1，i≠udist数组的变化过程求顶点0到其他顶点的最短路径kdistk[0]distk[1]distk[2]distk[3]distk[4]distk[5]distk[6]104-66∞∞∞204-660-2-10304-66-1-2-10404-66-1-2-10504-66-1-2-10604-66-1-2-10013452646-61761245-86path数组的变化过程kpathk[0]pathk[1]pathk[2]pathk[3]pathk[4]pathk[5]pathk[6]1-1000-1-1-12-10002253-10005254-10005255-10005256-1000525求顶点0到其他顶点的最短路径013452646-61761245-86最后求得的从顶点0到其他的顶点的最短路径长度和路径如下：从顶点0到顶点1的路径长度为:4，路径为:0，1从顶点0到顶点2的路径长度为:-6，路径为:0，2从顶点0到顶点3的路径长度为:6，路径为:0，3从顶点0到顶点4的路径长度为:-1，路径为:0，2，5，4从顶点0到顶点5的路径长度为:-2，路径为:0，2，5从顶点0到顶点6的路径长度为:-10，路径为:0，2，5，6013452646-61761245-862、贝尔曼-福特算法设计voidBellmanFord(MGraphg，intv){inti，k，u;

intdist[MAXV]，path[MAXV];

for(i=0;i<g.n;i++)

{dist[i]=g.edges[v][i]; //对dist(1)[i]初始化

if(i!=v&&dist[i]<INF)

path[i]=v; //对path(1)[i]初始化

else

path[i]=-1;

}

for(k=2;k<g.n;k++)

//从dist1[u]递推出dist2[u]，…，distn-1[u]循环n-1次

{for(u=0;u<g.n;u++)

//修改每个顶点的dist和path

{if(u!=v)

{ for(i=0;i<g.n;i++) //考虑其他每个顶点

{if(g.edges[i][u]<INF&& dist[u]>dist[i]+g.edges[i][u])

{ dist[u]=dist[i]+g.edges[i][u];

path[u]=i;

}

}

}

}

}

Dispath(g，dist，path，v); //输出最短路径及长度}贝尔曼-福特算法适合含有负权的图求最短路径。但如果存在从源点可达的负权值回路，则最短路径不存在，因为可以重复走这个回路，使得路径无穷小。

【算法分析】对于含有n个顶点e条边的带权有向图，贝尔曼-福特算法的时间复杂度为O(ne)，其正确性证明不再讨论。9.2.3SPFA算法

SPFA算法也是一个求单源最短路径的算法，全称是ShortestPathFasterAlgorithm（SPFA），是由西南交通大学段凡丁老师1994年发明的（见《西南交通大学学报》，1994，29（2），p207～212）。

当给定的图存在负权边时，狄克斯特拉不再适合，而贝尔曼-福特算法的时间复杂度又过高，此时可以采用SPFA算法，有人称SPFA算法是求最短路径的万能算法。但SPFA算法仍然不适合含负权回路的图。1.SPFA算法的求解思路

SPFA算法思想：设立一个队列qu用来保存待优化的结点，优化时每次出队顶点v，找到它的每个相邻点w，对顶点w进行松弛操作：

如果dist[w]>dist[v]+cost(v，w)（cost(v，w)表示顶点v到w的边权值），则修改dist[w]=dist[v]+cost(v，w)。

设置一维数组visited，visited[i]元素表示顶点i是否在队列qu中，初始时visited的所有元素设置为0。

仅仅将visited[i]=0的顶点i进队，一旦顶点i进队，置visited[i]=1，但顶点v出队后，有可能后面修改dist[v]，而dist[v]改变后，其相邻点需要重新松弛，所以出队的顶点v需要重新设置visited[v]=0，以便可以再次进队进行其相邻点松弛。这样的操作直到队列为空。2.SPFS算法设计

对于邻接表G，源点s，采用SPFS算法求顶点s的其他顶点的最短路径。

用STL的queue<int>容器作为队列qu，path数组存放路径，path[i]表示源点s到顶点i的最短路径上顶点i的前驱顶点。//问题表示ints;ALGraph*G;//求解结果表示intdist[MAXV];intpath[MAXV];voidSPFA() //求单源点s到其他各顶点的最短距离{ArcNode*p;intv,w;intvisited[MAXV]; //visited[i]表示顶点i是否在qu中queue<int>qu; //定义一个队列qufor(inti=0;i<G->n;i++) //初始化顶点s到i的距离{ dist[i]=INF; visited[i]=0; path[i]=-1;}dist[s]=0; //将源点的dist设为0visited[s]=1; //设置源点s的访问标记qu.push(s); //源点s进队while(!qu.empty()) //队不空循环{v=qu.front();qu.pop(); //出队顶点vvisited[v]=0; //释放对v的标记，可以重新进队p=G->adjlist[v].firstarc;while(p!=NULL) //处理顶点v的每个相邻点w{w=p->adjvex;if(dist[w]>dist[v]+p->weight) //如果不满足三角形性质{dist[w]=dist[v]+p->weight; //松弛dist[i]path[w]=v;}if(visited[w]==0) //顶点w没有访问{qu.push(w); //将顶点w进队visited[w]=1;}p=p->nextarc;}}}SPFA算法在形式上和广度优先遍历算法非常类似，不同的是广度优先遍历中一个顶点出了队列就不可能重新进入队列，而SPFA算法中一个顶点可能在出队之后再次进队。

【算法分析】SPFA算法中，while循环的执行次数大致为图中边数e，算法的时间复杂度为O(e)，由于e通常远小于n*(n+1)/2，所以好于狄克斯特拉算法。9.2.4弗洛伊德算法1、弗洛伊德算法的求解思路弗洛伊德算法基于动态规划方法。采用一个二维数组A存放当前顶点之间的最短路径长度，即分量A[i][j]表示当前顶点i到顶点j的最短路径长度，通过递推产生一个矩阵序列A0、A1、…、Ak、…、An-1。其中Ak[i][j]表示从顶点i到顶点j的路径上所经过的顶点编号不大于k的最短路径长度。ibjkapathk-1[i][j]=b，pathk-1[k][j]=a，若Ak-1[i][j]>Ak-1[i][k]+Ak-1[k][j]，选择经过顶点k的路径，即pathk[i][j]=a=pathk-1[k][j]。Ak[i][j]=min{Ak-1[i][j],Ak-1[i][k]+Ak-1[k][j]}Ak-1[i][j]Ak-1[i][k]Ak-1[k][j]调整方式归纳起来，弗洛伊德思想可用如下的表达式来描述：A-1[i][j]=g.edges[i][j]Ak[i][j]=MIN{Ak-1[i][j]，Ak-1[i][k]+Ak-1[k][j]}

0≤k≤n-1没有路径-13-1-12-12211-1-10-10-13210path-101∞∞2033240∞7∞503210A-1图G012353273124-13-1-101∞∞2-122203311-1-1240∞0-10-17∞5032103210A0path0考虑顶点0：没有任何路径修改图G012353273124-13-1-101∞∞2-122203311-1-1240∞010-1795032103210A1path1考虑顶点1：0→2：由无路径改为0→1→2，path[0][2]改为1图G012353273124012301230597-101070422-111330222-124410223-1A2path2考虑顶点2：1→0：由无路径改为1→2→0，path[1][0]改为23→1：由无路径改为3→2→1，path[3][1]改为23→0：由无路径改为3→2→0，path[3][0]改为2图G012353273124-132201442-122203313-122306030-1785032103210A3path3考虑顶点3：0→2：由0→1→2改为0→3→2，path[1][0]改为31→2：由1→2改为1→3→2，path[1][0]改为31→0：由1→2→0改为1→3→2→0，path[1][0]改为2求所有顶点之间最短路径完毕图G012353273124求最短路径长度：

由A3数组可以直接得到两个顶点之间的最短路径长度，如A3[1][0]=6，说明顶点1到0的最短路径长度为6。求最短路径：

以求顶点1到0的最短路径说明：path3[1][0]=2，说明顶点0的前一顶点是顶点2；path3[1][2]=3，表示顶点2的前一个顶点是顶点3；path3[1][3]=1，表示顶点3的前一个顶点是顶点1，找到起点1。依次得到的顶点序列为0、2、3、1，则顶点1到0的最短路径为1→3→2→0。012301230587-103060322-131330222-124410223-1A3path32、弗洛伊德算法设计voidFloyd(MGraphg){intA[MAXV][MAXV]，path[MAXV][MAXV];

inti，j，k;

for(i=0;i<g.n;i++)

for(j=0;j<g.n;j++)

{A[i][j]=g.edges[i][j];

if(i!=j&&g.edges[i][j]<INF)

path[i][j]=i; //顶点i到j有边时

else

path[i][j]=-1; //顶点i到j没有边时

}for(k=0;k<g.n;k++)

{for(i=0;i<g.n;i++)

for(j=0;j<g.n;j++)

if(A[i][j]>A[i][k]+A[k][j])

{A[i][j]=A[i][k]+A[k][j];

path[i][j]=path[k][j]; //修改最短路径

}

}

Dispath(g，A，path); //输出最短路径}弗洛伊德算法的时间复杂度为O(n3)，其中n为图中顶点个数。算法用途时间复杂度特点Dijkstra单源最短路径O(n2)不适合负权SPFA单源最短路径O(e)不适合负权回路Bellman-Ford单源最短路径O(ne)不适合负权回路Floyd多源最短路径O(n3)不适合负权回路算法比较9.3.1TSP问题描述

TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。

假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。9.3求解旅行商问题9.3.2采用蛮力法求解TSP问题02136858587589367

以右图所示的一个4城市图为例，假设TSP问题的起点为0，求出的所有从顶点0到顶点0并通过所有顶点的路径如下：路径1：0→1→2→3→0：28路径2：0→1→3→2→0：29路径3：0→2→1→3→0：26路径4：0→2→3→1→0：23路径5：0→3→2→1→0：59路径6：0→3→1→2→0：59

【算法分析】对于图中的n个顶点，求1～n-1全排列的时间为O(n×n!)，对于O(n!)的路径，求每条路径长度的时间为O(n)，所以算法的时间复杂度为O(n×n!)。9.3.3采用动态规划求解TSP问题

假设从顶点s（这里s=0）出发，令f(V，i)表示从顶点s出发经过V（一个顶点的集合）中所有顶点有且仅有一次到达顶点i的最短路径长度。0siVf(V，i):0s0Vf(V，0):f(V，0)的结果就是最终结果当V为空集，那么f(V，i)表示从顶点s不经过任何顶点到达顶点i，显然此时有f(V，i)=g.edges[s][i]。如果V不为空，对于jV，那么f(V-{j}，j)就是子问题的最优解。尝试V中的每个顶点j，并求出最优解：

f(V，i)=min{f(V-{j}，j)+g.edges[j][i]}0sjiV-{j]0siVmin0siV=Ø0sig.edges[s][i]对应的状态转移方程（s=0）如下：f(V，i)=g.edges[0][i] 当V={}f(V，i)=min(f(V-{j}，j)+g.edges[j][i]|jV}

当V≠{}f(V，0)的结果即为所求。

起点s=0，f({1，2，3}，0)就是从顶点0出发经过顶点1、2、3到达顶点0的最短路径长度。

从f({1，2，3}，0)出发进行递推，达到叶子结点后进行求值，求解结果为23，对应的最短路径是02310。02136858587589367采用STL的set<int>容器表示顶点集合V。对应的递归求解程序如下：typedefset<int>SET;//采用set<int>表示顶点集合//问题表示ints=0; //指定起点为0MGraphg; //图的邻接矩阵intf(SETV,inti) //求TSP所有解的路径长度{intminpathlen=INF; //最短路径长度if(V.size()==0) //当V为空时 returng.edges[0][i];else //当V为不空时{SET::iteratorit;for(it=V.begin();it!=V.end();++it) //扫描集合V中的顶点j{SETtmpV=V;intj=*it;tmpV.erase(j); //tmpV=V-{j}intpathlen=f(tmpV,j)+g.edges[j][i];minpathlen=min(minpathlen,pathlen);}returnminpathlen;}}f(V，i)=g.edges[0][i] 当V={}f(V，i)=min(f(V-{j}，j)+g.edges[j][i]|jV} 当V≠{}

【算法分析】对于图中的n个顶点，本算法需要对{1，2，…，n-1}的每个子集都要操作，时间复杂度是O(2n)，当n比较大时非常耗时的。9.3.4采用回溯法求解TSP问题

用f(V，i)求从顶点i出发经过V（它是一个顶点的集合）中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。minpath保存最短路径，minpathlen保存最短路径长度，V用set<int>容器表示，初始时V={1，2，3}。

用path、pathlen表示当前路径和路径长度，采用的剪枝规则是：当一个结点的当前路径长度大于minpathlen，该结点变成死结点。采用回溯法求解TSP问题的基本框架如下：f(V,i,path,pathlen){顶点i添加到path，求出pathlen;if(V为空){if(顶点i到起点s有边)

得到一条路径;

比较求minpath和minpathlen;}else{对于V中的每个顶点j;tmpV=V-{j};if(pathlen<minpathlen) //剪枝处理

f(tmpV,j,path,pathlen);}}02136858587589367typedefset<int>SET;//采用set<int>表示顶点集合//问题表示ints; //指定起点MGraphg; //图的邻接矩阵//求解过程表示intCount=1; //路径条数累计vector<int>minpath; //保存最短路径intminpathlen=INF; //保存最短路径长度voidTSP(SETV,inti,vector<int>path,intpathlen){intprev;if(path.size()>0) //path不为空prev=path.back(); //prev为路径上的最后一个顶点path.push_back(i); //添加当前顶点ipathlen+=g.edges[prev][i]; //累计路径长度if(V.size()==0) //找到一个叶子结点{if(g.edges[i][s]!=0&&g.edges[i][s]!=INF)

//顶点i到起点s有边{path.push_back(0); //路径中加入起点0pathlen+=g.edges[i][s]; //累计路径长度dispasolution(path,pathlen);//输出一条路径if(pathlen<minpathlen) //比较求最短路径{minpathlen=pathlen;minpath=path;}}}else //对于非叶子结点{SET::iteratorit;for(it=V.begin();it!=V.end();it++){SETtmpV=V;intj=*it; //选择顶点jtmpV.erase(j); //从V中删除顶点j得到tmpVif(pathlen<minpathlen) //剪枝TSP(tmpV,j,path,pathlen);//递归调用}}}

【算法分析】对于图中的n个顶点，本算法需要对{1，2，…，n-1}的每个子集都要操作，时间复杂度是O(2n)。9.3.5采用分枝限界法求解TSP问题

采用优先队列式分枝限界法求解，用STL的priority_queue<NodeType>容器作为优先队列，其中NodeType的类型声明如下：structNodeType

//队列结点类型{intv; //当前顶点intnum; //路径中的结点个数vector<int>path; //当前路径intpathlen; //当前路径长度intvisited[MAXV]; //顶点访问标记booloperator<(constNodeType&s)const{returnpathlen>s.pathlen; //pathlen越小越优先出队}};

用结点e的（e.v，e.num，e.pathlen）表示状态，对于图9.16，起点s=0，采用分枝限界法求解的解空间如下图所示，图中阴影框表示最优解结点，每个结点旁的数字表示结点出队的顺序，带的结点表示死结点。02136858587589367//问题表示ints; //指定起点MGraphg; //图的邻接矩阵//求解过程表示intCount=1; //路径条数累计vector<int>minpath; //保存最短路径intminpathlen=INF; //保存最短路径长度structNodeType //队列结点类型voidTSP() //分枝限界法求起点为s的TSP问题{NodeTypee,e1;priority_queue<NodeType>qu; //定义优先队列que.v=0; //建立起点s对应的结点ee.pathlen=0;e.path.push_back(0);e.num=1;memset(e.visited,0,sizeof(e.visited));e.visited[0]=1;qu.push(e); //根结点e进队while(!qu.empty()) //队不空循环{e=qu.top();qu.pop(); //出队结点eif(e.num==g.n) //到达叶子结点{ if(g.edges[e.v][s]!=0&&g.edges[e.v][s]!=INF)

//e.v到起点s有边 {e.path.push_back(s); //路径中加入起点s e.pathlen+=g.edges[e.v][s];

//另外计入从e.v到起点s的路径长度dispasolution(e.path,e.pathlen);if(e.pathlen<minpathlen) //比较求最短路径{minpathlen=e.pathlen;minpath=e.path; } }}else //非叶子结点{for(intj=1;j<g.n;j++) //j从顶点1到n-1循环{if(g.edges[e.v][j]!=0&&g.edges[e.v][j]!=INF)

//当前顶点到顶点j有边{if(e.visited[j]==1) //跳过路径中重复的顶点jcontinue;e1.v=j; //建立e.v的相邻顶点j对应的结点e1e1.num=e.num+1;e1.path=e.path;e1.path.push_back(j); //path添加顶点je1.pathlen=e.pathlen+g.edges[e.v][j];for(inti=0;i<g.n;i++) //复制visitede1.visited[i]=e.visited[i];if(e1.pathlen<minpathlen) //剪枝{e1.visited[j]=1;qu.push(e1);}}}}}}

【算法分析】对于图中的n个顶点，上述算法的时间复杂度为O(2n)。9.3.6采用贪心法求解TSP问题实际上TSP问题不满足贪心法的最优子结构性质，所以采用贪心法不一定得到最优解，但可以采用合理的贪心策略。如可以采用最近邻点策略，即从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。顶点0～顶点00182533619351706求出最短路径为：

0→2→3→1→0时间复杂度为O(n2)02136858587589367

实际上TSP问题不满足贪心法的最优子结构性质，所以采用贪心法不一定得到最优解，但可以采用合理的贪心策略。局部最优全局最优==?贪心法需要证明具有贪心选择性质和最优子结构性质。9.4.1相关概念

设带权有向图G=(V,E)表示一个网络，其中两个分别称为起点s和终点t的顶点，起点的入度为零，终点的出度为零，其余顶点称为中间点，有向边<u,v>上的权值cu,v表示从顶点u到v的容量。

下图就是一个网络，边上的数值表示容量。9.4网络流012453614108533867463

定义在边集合E上的一个函数f(u，v)为网络G上的一个流量函数（flowfunction），满足以下条件：容量限制（capacityconstraints）：V中的任意两个顶点u、v，满足f(u，v)≤c(u，v)，即一条边的流量不能超过它的容量。

斜对称（skewsymmetry）：V中的任意两个顶点u、v，满足f(u，v)=-f(v，u)。即u到v的流量必须是v到u的流量的相反值。流守恒（flowconservation）：V中的非s、t其他任意两个顶点u、v，满足，即顶点的净流量（出去的总流量减去进来的总流量）是零。满足上述条件的流量函数称为网络流（network-flows），简称为流。012453614108533867463012453614,1010,38,65,33,33,08,76,67,74,16,63,1f为网络流一个网络

由于流过网络的流量具有一定的方向，边的方向就是流量流过的方向，每一条边上的流量应小于其容量，中间点的流入量总和等于其流出量总和，对于起点和终点，总输出流量等于总输入流量。满足这些条件的流f称为可行流，可行流总是存在的。012453614,1010,38,65,33,33,08,76,67,74,16,63,1

如果所有的边的流量均取0，即对于所有的顶点u、v，f(u，v)=0，称此可行流为零流（zeroflow），这样的零流一定是可行流。

如果某一条边的流量f(u，v)=c(u，v)，则称流f(u，v)是饱和流，否则为非饱和流。f(u，v)>0的边称为非零流边。

最大网络流问题就是求一个这样的可行流f，其流量达到最大。012453614,1010,38,65,33,33,08,76,67,74,16,63,1流f的值定义为|f|=，即从起点s出发的总流（这里记号|·|表示流的值，并表示绝对值）。

在最大流问题中，给出一个具有起点s和终点t的网络G，从中找出从s到t的最大值流。

给定一个网络G=(V，E)，其流量函数为f，由f对应的残留网络或者剩余网络Gf=(V，Ef)，Gf中的边称为残留边：

若G中有边<u，v>且f(u，v)<c(u，v)，则对应的残留边<u，v>的流量=c(u，v)-f(u，v)（表示从顶点u到v可以增加的最大额外网络流量），若G中有边<u，v>且f(u，v)>0，则对应的残留边<v，u>的流量=f(u，v)（表示从顶点u到v可以减少的最大额外网络流量）。012453614,1010,38,65,33,33,08,76,67,74,16,63,1012453647262767362103331113

若f是G中的一个流，Gf是由G导出的残留网络，f'是Gf中的一个流，则f+f'是G中一个流，且其值|f+f'|=|f|+|f'|。

设μ是网络G中的一条从顶点u到顶点v的一条路径，在路径中与路径的方向一致的边称为前向边（为可以增加流量的边），其集合记为μ+；

在路径中与路径的方向相反的边称