第9章圖算法設(shè)計(jì)9.1求圖的最小生成樹(shù)9.2求圖的最短路徑9.3求解旅行商問(wèn)題9.4網(wǎng)絡(luò)流9.1.1最小生成樹(shù)的概念一個(gè)連通圖的生成樹(shù)是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有構(gòu)成一棵樹(shù)的n-1條邊。對(duì)于一個(gè)帶權(quán)（假定每條邊上的權(quán)均為大于零的數(shù)）連通無(wú)向圖G中的不同生成樹(shù)，其每棵樹(shù)的所有邊上的權(quán)值之和也可能不同；圖的所有生成樹(shù)中具有邊上的權(quán)值之和最小的樹(shù)稱為圖的最小生成樹(shù)。9.1求圖的最小生成樹(shù)9.1.2普里姆算法構(gòu)造最小生成樹(shù)1.普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程

普里姆（Prim）算法是一種構(gòu)造性算法。假設(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖，T=(U，TE)是G的最小生成樹(shù)，其中U是T的頂點(diǎn)集，TE是T的邊集，則由G構(gòu)造從起始頂點(diǎn)v出發(fā)的最小生成樹(shù)T的步驟如下：

（1）初始化U={v}。以v到其他頂點(diǎn)的所有邊為候選邊；

（2）重復(fù)以下步驟n-1次，使得其他n-1個(gè)頂點(diǎn)被加入到U中：

①以頂點(diǎn)集U和頂點(diǎn)集V-U之間的所有邊（稱為割集(U，V-U)）作為候選邊，從中挑選權(quán)值最小的邊（稱為輕邊）加入TE，設(shè)該邊在V-U中的頂點(diǎn)是k，將k加入U(xiǎn)中；②考察當(dāng)前V-U中的所有頂點(diǎn)j，修改候選邊：若(k，j)的權(quán)值小于原來(lái)和頂點(diǎn)j關(guān)聯(lián)的候選邊，則用(k，j)取代后者作為候選邊。504136218676534250413621663422.普里姆算法設(shè)計(jì)為了便于在集合U和V-U之間選擇權(quán)最小的邊，建立了兩個(gè)數(shù)組closest和lowcost，它們記錄從U到V-U具有最小權(quán)值的邊，對(duì)于某個(gè)j∈V-U，closest[j]存儲(chǔ)該邊依附的在U中的頂點(diǎn)編號(hào)，lowcost[j]存儲(chǔ)該邊的權(quán)值。closest[j]vkjlowcost[j]V-U={j|lowcost[j]≠0U={i|lowcost[i]=0增量過(guò)程（V-U的頂點(diǎn)一個(gè)一個(gè)添加到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中頂點(diǎn)j：g.edges[k][j]<lowcost[j]調(diào)整 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數(shù)組{ lowcost[j]=g.edges[v][j]; closest[j]=v;}

Prim(g，v)算法利用上述過(guò)程構(gòu)造最小生成樹(shù)，其中參數(shù)g為帶權(quán)鄰接矩陣，v為起始頂點(diǎn)的編號(hào)。for(i=1;i<g.n;i++) //找出(n-1)個(gè)頂點(diǎn){ mincost=INF;

for(j=0;j<g.n;j++) //在(V-U)中找出離U最近的頂點(diǎn)k if(lowcost[j]!=0&&lowcost[j]<mincost) {mincost=lowcost[j]; k=j; //k記錄最近頂點(diǎn)的編號(hào) }

printf("邊(%d,%d)權(quán)為:%d\n",closest[k],k,mincost); lowcost[k]=0; //標(biāo)記k已經(jīng)加入U(xiǎn) for(j=0;j<g.n;j++) //修改數(shù)組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循環(huán)，所以時(shí)間復(fù)雜度為O(n2)，其中n為圖的頂點(diǎn)個(gè)數(shù)。3.普里姆算法的正確性證明

普里姆算法是一種貪心算法。對(duì)于帶權(quán)連通無(wú)向圖G=(V，E)，采用通過(guò)對(duì)算法步驟的歸納來(lái)證明普里姆算法的正確性。

定理9.1對(duì)于任意正整數(shù)k<n，存在一棵最小生成樹(shù)T包含Prim算法前k步選擇的邊。

證明：

（1）k=1時(shí)，用反證法證明存在一棵最小生成樹(shù)T包含e=(0，i)，其中(0，i)是所有關(guān)聯(lián)頂點(diǎn)0的邊中權(quán)最小的。

令T為一棵最小生成樹(shù)，假如T不包含(0，i)，那么根據(jù)命題9.1，T∪{(0，i)}含有一個(gè)回路，設(shè)這個(gè)回路中關(guān)聯(lián)頂點(diǎn)0的邊是(0，j)，

令：T'=(T-{(0，j)})∪{(0，i)}則T'也是一棵生成樹(shù)，并且所有邊權(quán)值和更小（除非(0，i)與(0，j)的權(quán)相同），與T為一棵最小生成樹(shù)矛盾。

（2）假設(shè)算法進(jìn)行了k-1步，生成樹(shù)的邊為e1，e2，…，ek-1，這些邊的k個(gè)端點(diǎn)構(gòu)成集合U，并且存在G的一棵最小生成樹(shù)T包含這些邊。

（3）算法第k步選擇了頂點(diǎn)ik，則ik到U中頂點(diǎn)的邊的權(quán)值最小，設(shè)這條邊為ek=(ik，il)。假設(shè)最小生成樹(shù)T不含有邊ek，將ek添加到T中形成一個(gè)回路，如下圖所示：ilikekUV-Uxye'

這個(gè)回路一定有連接U與V-U中頂點(diǎn)的邊e'，用ek替換e'得到樹(shù)T'，即：T'=(T-{e'})∪{ek}則T'也是一棵生成樹(shù)，包含邊e1，e2，…，ek-1，ek，并且T'所有邊權(quán)值和更小（除非e'與ek的權(quán)相同），與T為一棵最小生成樹(shù)矛盾。定理即證。

當(dāng)k=n時(shí)，U包含G中所有頂點(diǎn)，由普里姆算法構(gòu)造的T=（U，TE）就是G的最小生成樹(shù)。ilikekUV-Uxye'9.3.3克魯斯卡爾算法1.克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程克魯斯卡爾（Kruskal）算法是一種按權(quán)值的遞增次序選擇合適的邊來(lái)構(gòu)造最小生成樹(shù)的方法。假設(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)e條邊的帶權(quán)連通無(wú)向圖，T=(U，TE)是G的最小生成樹(shù)，則構(gòu)造最小生成樹(shù)的步驟如下：①置U的初值等于V（即包含有G中的全部頂點(diǎn)），TE的初值為空集（即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量）。②將圖G中的邊按權(quán)值從小到大的順序依次選取：若選取的邊未使生成樹(shù)T形成回路，則加入TE；否則舍棄，直到TE中包含n-1條邊為止。504136218676534250413621663422.克魯斯卡爾算法設(shè)計(jì)實(shí)現(xiàn)克魯斯卡爾算法的關(guān)鍵是如何判斷選取的邊是否與生成樹(shù)中已有的邊形成回路，這可以通過(guò)并查集來(lái)解決。

對(duì)于一個(gè)數(shù)據(jù)序列和一個(gè)等價(jià)關(guān)系，并查集支持查找一個(gè)元素所屬的集合以及兩個(gè)元素各自所屬的集合的合并等運(yùn)算，同一集合中的元素滿足等價(jià)關(guān)系。當(dāng)給出兩個(gè)元素滿足等價(jià)關(guān)系構(gòu)成一個(gè)無(wú)序?qū)?a，b)時(shí)，需要快速“合并”a和b分別所在的集合，這其間需要反復(fù)“查找”某元素所在的集合。“并”、“查”和“集”三字由此而來(lái)。

在這種數(shù)據(jù)結(jié)構(gòu)中，n個(gè)不同的元素被分為若干組，每組是一個(gè)集合，這種集合叫做分離集合。可以采用有根樹(shù)來(lái)表示集合，樹(shù)中的每個(gè)結(jié)點(diǎn)包含集合的一個(gè)元素，每棵樹(shù)表示一個(gè)集合。多個(gè)集合形成一個(gè)森林，以每棵樹(shù)的根結(jié)點(diǎn)編號(hào)唯一標(biāo)識(shí)該集合，并且根結(jié)點(diǎn)的父結(jié)點(diǎn)指向其自身，樹(shù)上的其他結(jié)點(diǎn)都用一個(gè)父指針表示它的附屬關(guān)系。1234（1,3）1234（2,3）1234采用順序方法即采用一個(gè)數(shù)組t來(lái)存儲(chǔ)森林，其中結(jié)點(diǎn)的類型定義如下：typedefstructnode{intdata; //結(jié)點(diǎn)對(duì)應(yīng)頂點(diǎn)編號(hào)

intrank; //結(jié)點(diǎn)對(duì)應(yīng)秩

intparent; //結(jié)點(diǎn)對(duì)應(yīng)雙親下標(biāo)}UFSTree; //并查集樹(shù)的結(jié)點(diǎn)類型并查集的基本運(yùn)算算法如下：voidMAKE_SET(UFSTreet[],intn) //初始化并查集樹(shù){for(inti=0;i<n;i++) //頂點(diǎn)編號(hào)為0～(n-1){t[i].rank=0; //秩初始化為0t[i].parent=i; //雙親初始化指向自已}}intFIND_SET(UFSTreet[],intx) //在x所在子樹(shù)中查找集合的編號(hào){if(x!=t[x].parent) //若雙親不是自已return(FIND_SET(t,t[x].parent)); //遞歸在雙親中找xelsereturn(x); //若雙親是自已,返回x}voidUNION(UFSTreet[],intx,inty) //將x和y所在的子樹(shù)合并{x=FIND_SET(t,x);y=FIND_SET(t,y);if(t[x].rank>t[y].rank) //x結(jié)點(diǎn)的秩大于y結(jié)點(diǎn)的秩 t[y].parent=x; //將x結(jié)點(diǎn)作為y的雙親結(jié)點(diǎn)else //y結(jié)點(diǎn)的秩大于等于x結(jié)點(diǎn)的秩{t[x].parent=y; //將y結(jié)點(diǎn)作為x的雙親結(jié)點(diǎn)if(t[x].rank==t[y].rank) //x和y結(jié)點(diǎn)的秩相同t[y].rank++; //y結(jié)點(diǎn)的秩增1}}對(duì)于n元素構(gòu)成的分離集合樹(shù)，其高度最高為log2n，所以FIND_SET(t，x)和UNION(t，x，y)算法的時(shí)間復(fù)雜度均為O(log2n)。用一個(gè)數(shù)組E[]存放圖G中的所有邊，要求它們是按權(quán)值從小到大的順序排列的，為此先從圖G的鄰接矩陣中獲取所有邊集E，再采用推排序法對(duì)邊集E按權(quán)值遞增排序。

數(shù)組E的元素類型定義如下：typedefstruct{intu; //邊的起始頂點(diǎn)

intv; //邊的終止頂點(diǎn)

intw; //邊的權(quán)值}Edge;對(duì)應(yīng)的克魯斯卡爾算法如下：voidKruskal(MGraphg) //Kruskal算法{inti,j,k,u1,v1,sn1,sn2;UFSTreet[MaxSize];EdgeE[MaxSize];k=0;for(i=0;i<g.n;i++) //由g下三角部分產(chǎn)生的邊集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);

//調(diào)用STL的sort()算法按w遞增排序MAKE_SET(t,g.n); //初始化并查集樹(shù)tk=1; //k表示當(dāng)前構(gòu)造生成樹(shù)的第幾條邊,初值為1j=0; //E中邊的下標(biāo),初值為0while(k<g.n) //生成的邊數(shù)小于n時(shí)循環(huán){u1=E[j].u;v1=E[j].v; //取一條邊的頭尾頂點(diǎn)編號(hào)u1和v2sn1=FIND_SET(t,u1);sn2=FIND_SET(t,v1); //分別得到兩個(gè)頂點(diǎn)所屬的集合編號(hào)if(sn1!=sn2)

//添加該邊不會(huì)構(gòu)成回路,將其作為最小生成樹(shù)的一條邊輸出{printf("(%d,%d):%d\n",u1,v1,E[j].w);k++; //生成邊數(shù)增1UNION(t,u1,v1); //將u1和v1兩個(gè)頂點(diǎn)合并}j++; //掃描下一條邊}}上述克魯斯卡爾算法構(gòu)造最小生成樹(shù)的時(shí)間復(fù)雜度為O(elog2e)。3.克魯斯卡爾算法的正確性證明

克魯斯卡爾算法也是一種貪心算法。對(duì)于帶權(quán)連通無(wú)向圖G=(V，E)，采用通過(guò)對(duì)算法產(chǎn)生T=(V，TE)的邊數(shù)k的歸納步驟來(lái)證明克魯斯卡爾算法的正確性。

定理9.2克魯斯卡爾算法可以找到一棵最小生成樹(shù)。

證明：

（1）k=1時(shí)，首先T中沒(méi)有任何邊，設(shè)e1是G中權(quán)最小的邊，加入e1不會(huì)產(chǎn)生任何回路。顯然是正確的。

（2）假設(shè)算法進(jìn)行了k-1步產(chǎn)生k-1條邊，即e1，e2，…，ek-1，對(duì)應(yīng)的邊集合為T(mén)E1，產(chǎn)生的T1=(V1，TE1)是最小生成樹(shù)T的子樹(shù)（V1為T(mén)E1中的頂點(diǎn)集）。

（3）算法第k步選擇了邊e=(v，u)，設(shè)TE2=TE1∪{e}，TE2中的邊把G中頂點(diǎn)分成兩個(gè)或者兩個(gè)以上的連通分量。

設(shè)S1是添加邊e后包含頂點(diǎn)v的連通分量的頂點(diǎn)集，S2是添加邊e后包含頂點(diǎn)u的連通分量的頂點(diǎn)集。

顯然e是離開(kāi)S的最短邊之一（因?yàn)橹八休^短邊都已經(jīng)考察過(guò)，它們或者添加到T中，或者因?yàn)樵谕粋€(gè)連通分量中而被丟棄）。

現(xiàn)要證明T2=(V2，TE2)也是最小生成樹(shù)的子樹(shù)（V2為T(mén)E2中的頂點(diǎn)集）。vueS1S2xye'

若最終的最小生成樹(shù)T包含e=(v，u)，那么就不需要再進(jìn)一步證明了。否則在T中S1和S2之間一定存在一條邊e'=(x，y)（在后面添加的），現(xiàn)在再在S1和S2之間添加邊e得必構(gòu)成一個(gè)回路，如下圖所示：

顯然e'的權(quán)值大于或等于e的權(quán)值即cost(e')≥cost(e)，否則邊e'應(yīng)該在前面添加，這樣由S1和S2加上e1構(gòu)成的生成樹(shù)的權(quán)值和大于等于T2的權(quán)值和，說(shuō)明T不是最小生成樹(shù)，與T是最小生成樹(shù)的假設(shè)矛盾，從而證明T2是最小生成樹(shù)的子樹(shù)。當(dāng)k=n-1時(shí)，由克魯斯卡爾算法構(gòu)造的T=(V，TE)就是G的最小生成樹(shù)。對(duì)于帶權(quán)圖，考慮路徑上各邊上的權(quán)值，則通常把一條路徑上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長(zhǎng)度或稱帶權(quán)路徑長(zhǎng)度。從源點(diǎn)到終點(diǎn)可能不止一條路徑，把帶權(quán)路徑長(zhǎng)度最短的那條路徑稱為最短路徑，其路徑長(zhǎng)度（權(quán)值之和）稱為最短路徑長(zhǎng)度或者最短距離。9.2求圖的最短路徑9.2.1狄克斯特拉算法1、狄克斯特拉算法的求解步驟基本思想是：設(shè)G=(V，E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組：

第1組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑v，…，u，就將u加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了）。

第2組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第2組的頂點(diǎn)加入S中。具體步驟：初始時(shí)，S只包含源點(diǎn)，即S={v}，頂點(diǎn)v到自已的距離為0。U包含除v外的其他頂點(diǎn)，v到U中頂點(diǎn)i的距離為邊上的權(quán)（若v與i有邊<v，i>）或∞（若i不是v的出邊鄰接點(diǎn)）。具體步驟：從U中選取一個(gè)頂點(diǎn)u，頂點(diǎn)v到頂點(diǎn)u的距離最小，然后把頂點(diǎn)u加入S中（該選定的距離就是v到u的最短路徑長(zhǎng)度）。以頂點(diǎn)u為新考慮的中間點(diǎn)，修改頂點(diǎn)v到U中各頂點(diǎn)的距離：若從源點(diǎn)v到頂點(diǎn)j（j∈U）經(jīng)過(guò)頂點(diǎn)u的距離（圖中為cvu+wuj）比原來(lái)不經(jīng)過(guò)頂點(diǎn)u距離（圖中為cvj）短，則修改從頂點(diǎn)v到頂點(diǎn)j的最短距離值（圖中修改為cvu+wuj）。uvjcvucvjcuj兩條路徑中取最短者重復(fù)步驟②和③直到S包含所有的頂點(diǎn)。2、狄克斯特拉算法設(shè)計(jì)設(shè)置一個(gè)數(shù)組dist[0..n-1]，dist[i]用來(lái)保存從源點(diǎn)v到頂點(diǎn)i的目前最短路徑長(zhǎng)度，它的初值為<v，i>邊上的權(quán)值，若頂點(diǎn)v到頂點(diǎn)i沒(méi)有邊，則權(quán)值定為∞。以后每考慮一個(gè)新的中間點(diǎn)時(shí)，dist[i]的值可能被修改而變小。

設(shè)置一個(gè)數(shù)組path[0..n-1]用于保存最短路徑。path[j]保存當(dāng)前最短路徑中的前一個(gè)頂點(diǎn)的編號(hào)，它的初值為源點(diǎn)v的編號(hào)（頂點(diǎn)v到頂點(diǎn)j有邊時(shí)）或-1（頂點(diǎn)v到頂點(diǎn)i無(wú)邊時(shí)）。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; //頂點(diǎn)v到頂點(diǎn)i有邊時(shí)，置頂點(diǎn)i的前一個(gè)頂點(diǎn)為velsepath[i]=-1; //頂點(diǎn)v到頂點(diǎn)i沒(méi)邊時(shí)，置頂點(diǎn)i的前一個(gè)頂點(diǎn)為-1}S[v]=1;path[v]=0; //源點(diǎn)編號(hào)v放入s中for(i=0;i<g.n;i++) //循環(huán)直到所有頂點(diǎn)的最短路徑都求出{mindis=INF; //mindis求最小路徑長(zhǎng)度f(wàn)or(j=0;j<g.n;j++) //選取不在s中且具有最小距離的頂點(diǎn)uif(S[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}S[u]=1;

//頂點(diǎn)u加入s中for(j=0;j<g.n;j++) //修改不在S中的頂點(diǎn)的距離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); 輸出最短路徑}狄克斯特拉算法的時(shí)間復(fù)雜度為O(n2)，其中n為圖中頂點(diǎn)個(gè)數(shù)。3、狄克斯特拉算法的正確性證明

狄克斯特拉算法也是一種貪心算法。證明Dijkstra算法可以找到圖中從源點(diǎn)v到其他所有頂點(diǎn)的最短路徑長(zhǎng)度。用數(shù)學(xué)歸納法證明：

（1）如果頂點(diǎn)j在S中，則dist[i]給出了從源點(diǎn)到頂點(diǎn)i的最短路徑長(zhǎng)度。（2）如果頂點(diǎn)j不在S中，則dist[j]給出了從源點(diǎn)到頂點(diǎn)j的最短特殊路徑長(zhǎng)度，即該路徑上的所有中間頂點(diǎn)都屬于S。證明：初始時(shí)S中只有一個(gè)源點(diǎn)v，到其他頂點(diǎn)的路徑就是從源點(diǎn)到相應(yīng)頂點(diǎn)的邊，顯然（1）、（2）是成立的。假設(shè)向S中添加一個(gè)新頂點(diǎn)u之前，條件（1）、（2）都成立。（1）如果頂點(diǎn)j在S中，則dist[i]給出了從源點(diǎn)到頂點(diǎn)i的最短路徑長(zhǎng)度。（2）如果頂點(diǎn)j不在S中，則dist[j]給出了從源點(diǎn)到頂點(diǎn)j的最短特殊路徑長(zhǎng)度，即該路徑上的所有中間頂點(diǎn)都屬于S。

條件（1）的歸納步驟：對(duì)于每個(gè)在添加之前已經(jīng)存在于S中的頂點(diǎn)u，不會(huì)有任何變化，條件（1）依然成立。

在頂點(diǎn)u加入到S之前，由假設(shè)可知dist[u]是源點(diǎn)到u的最短路徑長(zhǎng)度，還要驗(yàn)證從源點(diǎn)v到頂點(diǎn)u的最短路徑?jīng)]有經(jīng)過(guò)任何不在S中的頂點(diǎn)。

假設(shè)存在這種情況，即沿著從源點(diǎn)v到頂點(diǎn)u的最短路徑前進(jìn)時(shí)，會(huì)遇到一個(gè)或多個(gè)不屬于S的頂點(diǎn)（不含頂點(diǎn)u自已），設(shè)x是第一個(gè)這樣的頂點(diǎn)，如下圖所示。vxuS該路徑的初始部分即從源點(diǎn)v到頂點(diǎn)x的部分是一條特殊路徑，由假設(shè)的條件（2），dist[x]是源點(diǎn)v到頂點(diǎn)x的最短特殊路徑長(zhǎng)度，由于邊非負(fù)，因此經(jīng)過(guò)x到u的距離肯定不短于到x的距離。

又因?yàn)樗惴ㄔ趚之前選擇頂點(diǎn)u，因此dist[x]不小于dist[u]，這樣經(jīng)過(guò)x到u的距離就至少是dist[u]，所以經(jīng)過(guò)x到u的最短路徑不短于到u的最短特殊路徑。

現(xiàn)在驗(yàn)證了當(dāng)u加到S中時(shí)，dist[u]確定給出源點(diǎn)v到頂點(diǎn)u的最短路徑長(zhǎng)度，條件（1）是成立的。vxuS（1）如果頂點(diǎn)j在S中，則dist[i]給出了從源點(diǎn)到頂點(diǎn)i的最短路徑長(zhǎng)度。（2）如果頂點(diǎn)j不在S中，則dist[j]給出了從源點(diǎn)到頂點(diǎn)j的最短特殊路徑長(zhǎng)度，即該路徑上的所有中間頂點(diǎn)都屬于S。

條件（2）的歸納步驟：考慮不屬于S且不同于u的一個(gè)頂點(diǎn)w，當(dāng)u加到S中時(shí)，從源點(diǎn)v到w的最短特殊路徑有兩種可能：或者不會(huì)變化，或者現(xiàn)在經(jīng)過(guò)頂點(diǎn)u（也可能經(jīng)過(guò)S中的其他頂點(diǎn)）。

對(duì)于第2種情況，設(shè)x是到達(dá)w之前經(jīng)過(guò)的S的最后一個(gè)頂點(diǎn)，因此這條路徑的長(zhǎng)度就是dist[x]+L(x，w)（L(x，w)為頂點(diǎn)x到頂點(diǎn)w的路徑長(zhǎng)度）。對(duì)于任意S中的頂點(diǎn)x（包括u），要計(jì)算dist[w]的值，就必須比較dist[w]原先的值和dist[x]+L(x，w)的大小。

因?yàn)樗惴鞔_地進(jìn)行這種比較以計(jì)算新的dist[w]值，所以往S中加入新頂點(diǎn)u時(shí)，dist[w]仍然給出源點(diǎn)v到頂點(diǎn)w的最短特殊路徑的長(zhǎng)度，因此條件（2）也是成立的。9.4.2貝爾曼-福特算法1、貝爾曼-福特算法的求解思路貝爾曼-福特算法構(gòu)造一個(gè)最短路徑長(zhǎng)度數(shù)組序列dist1[u]、dist2[u]、…、distn-1[u]。dist1[u]為源點(diǎn)v到終點(diǎn)u的只經(jīng)過(guò)一條邊的最短路徑長(zhǎng)度。dist2[u]為源點(diǎn)v最多經(jīng)過(guò)兩條邊到達(dá)終點(diǎn)u最短路徑長(zhǎng)度。dist3[u]為源點(diǎn)v出發(fā)最多經(jīng)過(guò)不構(gòu)成負(fù)權(quán)值回路的三條邊到達(dá)終點(diǎn)u的最短路徑長(zhǎng)度，…。distn-1[u]為源點(diǎn)v出發(fā)最多經(jīng)過(guò)不構(gòu)成負(fù)權(quán)值回路的n-1條邊到達(dá)終點(diǎn)u的最短路徑長(zhǎng)度。算法的最終目的是計(jì)算出distn-1[u]。設(shè)已經(jīng)求出distk-1[u]（0≤k≤n-1），即從源點(diǎn)v最多經(jīng)過(guò)不構(gòu)成負(fù)權(quán)值回路的k-1條邊到達(dá)終點(diǎn)u的最短路徑長(zhǎng)度，從圖的鄰接矩陣g中可以找到各個(gè)頂點(diǎn)i到達(dá)頂點(diǎn)u的距離g.edges[i][u]。

計(jì)算MIN{distk-1[i]+g.edges[i][u]}，可以得到從源點(diǎn)v繞過(guò)各個(gè)頂點(diǎn)最多經(jīng)過(guò)不成負(fù)值回路的k條邊到達(dá)終點(diǎn)u的最短路徑的長(zhǎng)度，比較distk-1[u]和MIN{distk-1[i]+g.edges[i][u]}，取較小者作為distk[u]的值。所以得到以下遞推關(guān)系式：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數(shù)組的變化過(guò)程求頂點(diǎn)0到其他頂點(diǎn)的最短路徑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數(shù)組的變化過(guò)程kpathk[0]pathk[1]pathk[2]pathk[3]pathk[4]pathk[5]pathk[6]1-1000-1-1-12-10002253-10005254-10005255-10005256-1000525求頂點(diǎn)0到其他頂點(diǎn)的最短路徑013452646-61761245-86最后求得的從頂點(diǎn)0到其他的頂點(diǎn)的最短路徑長(zhǎng)度和路徑如下：從頂點(diǎn)0到頂點(diǎn)1的路徑長(zhǎng)度為:4，路徑為:0，1從頂點(diǎn)0到頂點(diǎn)2的路徑長(zhǎng)度為:-6，路徑為:0，2從頂點(diǎn)0到頂點(diǎn)3的路徑長(zhǎng)度為:6，路徑為:0，3從頂點(diǎn)0到頂點(diǎn)4的路徑長(zhǎng)度為:-1，路徑為:0，2，5，4從頂點(diǎn)0到頂點(diǎn)5的路徑長(zhǎng)度為:-2，路徑為:0，2，5從頂點(diǎn)0到頂點(diǎn)6的路徑長(zhǎng)度為:-10，路徑為:0，2，5，6013452646-61761245-862、貝爾曼-福特算法設(shè)計(jì)voidBellmanFord(MGraphg，intv){inti，k，u;

intdist[MAXV]，path[MAXV];

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

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

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

path[i]=v; //對(duì)path(1)[i]初始化

else

path[i]=-1;

}

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

//從dist1[u]遞推出dist2[u]，…，distn-1[u]循環(huán)n-1次

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

//修改每個(gè)頂點(diǎn)的dist和path

{if(u!=v)

{ for(i=0;i<g.n;i++) //考慮其他每個(gè)頂點(diǎn)

{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); //輸出最短路徑及長(zhǎng)度}貝爾曼-福特算法適合含有負(fù)權(quán)的圖求最短路徑。但如果存在從源點(diǎn)可達(dá)的負(fù)權(quán)值回路，則最短路徑不存在，因?yàn)榭梢灾貜?fù)走這個(gè)回路，使得路徑無(wú)窮小。

【算法分析】對(duì)于含有n個(gè)頂點(diǎn)e條邊的帶權(quán)有向圖，貝爾曼-福特算法的時(shí)間復(fù)雜度為O(ne)，其正確性證明不再討論。9.2.3SPFA算法

SPFA算法也是一個(gè)求單源最短路徑的算法，全稱是ShortestPathFasterAlgorithm（SPFA），是由西南交通大學(xué)段凡丁老師1994年發(fā)明的（見(jiàn)《西南交通大學(xué)學(xué)報(bào)》，1994，29（2），p207～212）。

當(dāng)給定的圖存在負(fù)權(quán)邊時(shí)，狄克斯特拉不再適合，而貝爾曼-福特算法的時(shí)間復(fù)雜度又過(guò)高，此時(shí)可以采用SPFA算法，有人稱SPFA算法是求最短路徑的萬(wàn)能算法。但SPFA算法仍然不適合含負(fù)權(quán)回路的圖。1.SPFA算法的求解思路

SPFA算法思想：設(shè)立一個(gè)隊(duì)列qu用來(lái)保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時(shí)每次出隊(duì)頂點(diǎn)v，找到它的每個(gè)相鄰點(diǎn)w，對(duì)頂點(diǎn)w進(jìn)行松弛操作：

如果dist[w]>dist[v]+cost(v，w)（cost(v，w)表示頂點(diǎn)v到w的邊權(quán)值），則修改dist[w]=dist[v]+cost(v，w)。

設(shè)置一維數(shù)組visited，visited[i]元素表示頂點(diǎn)i是否在隊(duì)列qu中，初始時(shí)visited的所有元素設(shè)置為0。

僅僅將visited[i]=0的頂點(diǎn)i進(jìn)隊(duì)，一旦頂點(diǎn)i進(jìn)隊(duì)，置visited[i]=1，但頂點(diǎn)v出隊(duì)后，有可能后面修改dist[v]，而dist[v]改變后，其相鄰點(diǎn)需要重新松弛，所以出隊(duì)的頂點(diǎn)v需要重新設(shè)置visited[v]=0，以便可以再次進(jìn)隊(duì)進(jìn)行其相鄰點(diǎn)松弛。這樣的操作直到隊(duì)列為空。2.SPFS算法設(shè)計(jì)

對(duì)于鄰接表G，源點(diǎn)s，采用SPFS算法求頂點(diǎn)s的其他頂點(diǎn)的最短路徑。

用STL的queue<int>容器作為隊(duì)列qu，path數(shù)組存放路徑，path[i]表示源點(diǎn)s到頂點(diǎn)i的最短路徑上頂點(diǎn)i的前驅(qū)頂點(diǎn)。//問(wèn)題表示ints;ALGraph*G;//求解結(jié)果表示intdist[MAXV];intpath[MAXV];voidSPFA() //求單源點(diǎn)s到其他各頂點(diǎn)的最短距離{ArcNode*p;intv,w;intvisited[MAXV]; //visited[i]表示頂點(diǎn)i是否在qu中queue<int>qu; //定義一個(gè)隊(duì)列qufor(inti=0;i<G->n;i++) //初始化頂點(diǎn)s到i的距離{ dist[i]=INF; visited[i]=0; path[i]=-1;}dist[s]=0; //將源點(diǎn)的dist設(shè)為0visited[s]=1; //設(shè)置源點(diǎn)s的訪問(wèn)標(biāo)記qu.push(s); //源點(diǎn)s進(jìn)隊(duì)while(!qu.empty()) //隊(duì)不空循環(huán){v=qu.front();qu.pop(); //出隊(duì)頂點(diǎn)vvisited[v]=0; //釋放對(duì)v的標(biāo)記，可以重新進(jìn)隊(duì)p=G->adjlist[v].firstarc;while(p!=NULL) //處理頂點(diǎn)v的每個(gè)相鄰點(diǎn)w{w=p->adjvex;if(dist[w]>dist[v]+p->weight) //如果不滿足三角形性質(zhì){dist[w]=dist[v]+p->weight; //松弛dist[i]path[w]=v;}if(visited[w]==0) //頂點(diǎn)w沒(méi)有訪問(wèn){qu.push(w); //將頂點(diǎn)w進(jìn)隊(duì)visited[w]=1;}p=p->nextarc;}}}SPFA算法在形式上和廣度優(yōu)先遍歷算法非常類似，不同的是廣度優(yōu)先遍歷中一個(gè)頂點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，而SPFA算法中一個(gè)頂點(diǎn)可能在出隊(duì)之后再次進(jìn)隊(duì)。

【算法分析】SPFA算法中，while循環(huán)的執(zhí)行次數(shù)大致為圖中邊數(shù)e，算法的時(shí)間復(fù)雜度為O(e)，由于e通常遠(yuǎn)小于n*(n+1)/2，所以好于狄克斯特拉算法。9.2.4弗洛伊德算法1、弗洛伊德算法的求解思路弗洛伊德算法基于動(dòng)態(tài)規(guī)劃方法。采用一個(gè)二維數(shù)組A存放當(dāng)前頂點(diǎn)之間的最短路徑長(zhǎng)度，即分量A[i][j]表示當(dāng)前頂點(diǎn)i到頂點(diǎn)j的最短路徑長(zhǎng)度，通過(guò)遞推產(chǎn)生一個(gè)矩陣序列A0、A1、…、Ak、…、An-1。其中Ak[i][j]表示從頂點(diǎn)i到頂點(diǎn)j的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度。ibjkapathk-1[i][j]=b，pathk-1[k][j]=a，若Ak-1[i][j]>Ak-1[i][k]+Ak-1[k][j]，選擇經(jīng)過(guò)頂點(diǎn)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]調(diào)整方式歸納起來(lái)，弗洛伊德思想可用如下的表達(dá)式來(lái)描述：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沒(méi)有路徑-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考慮頂點(diǎn)0：沒(méi)有任何路徑修改圖G012353273124-13-1-101∞∞2-122203311-1-1240∞010-1795032103210A1path1考慮頂點(diǎn)1：0→2：由無(wú)路徑改為0→1→2，path[0][2]改為1圖G012353273124012301230597-101070422-111330222-124410223-1A2path2考慮頂點(diǎn)2：1→0：由無(wú)路徑改為1→2→0，path[1][0]改為23→1：由無(wú)路徑改為3→2→1，path[3][1]改為23→0：由無(wú)路徑改為3→2→0，path[3][0]改為2圖G012353273124-132201442-122203313-122306030-1785032103210A3path3考慮頂點(diǎn)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求所有頂點(diǎn)之間最短路徑完畢圖G012353273124求最短路徑長(zhǎng)度：

由A3數(shù)組可以直接得到兩個(gè)頂點(diǎn)之間的最短路徑長(zhǎng)度，如A3[1][0]=6，說(shuō)明頂點(diǎn)1到0的最短路徑長(zhǎng)度為6。求最短路徑：

以求頂點(diǎn)1到0的最短路徑說(shuō)明：path3[1][0]=2，說(shuō)明頂點(diǎn)0的前一頂點(diǎn)是頂點(diǎn)2；path3[1][2]=3，表示頂點(diǎn)2的前一個(gè)頂點(diǎn)是頂點(diǎn)3；path3[1][3]=1，表示頂點(diǎn)3的前一個(gè)頂點(diǎn)是頂點(diǎn)1，找到起點(diǎn)1。依次得到的頂點(diǎn)序列為0、2、3、1，則頂點(diǎn)1到0的最短路徑為1→3→2→0。012301230587-103060322-131330222-124410223-1A3path32、弗洛伊德算法設(shè)計(jì)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; //頂點(diǎn)i到j(luò)有邊時(shí)

else

path[i][j]=-1; //頂點(diǎn)i到j(luò)沒(méi)有邊時(shí)

}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); //輸出最短路徑}弗洛伊德算法的時(shí)間復(fù)雜度為O(n3)，其中n為圖中頂點(diǎn)個(gè)數(shù)。算法用途時(shí)間復(fù)雜度特點(diǎn)Dijkstra單源最短路徑O(n2)不適合負(fù)權(quán)SPFA單源最短路徑O(e)不適合負(fù)權(quán)回路Bellman-Ford單源最短路徑O(ne)不適合負(fù)權(quán)回路Floyd多源最短路徑O(n3)不適合負(fù)權(quán)回路算法比較9.3.1TSP問(wèn)題描述

TSP問(wèn)題（TravellingSalesmanProblem）又譯為旅行推銷員問(wèn)題、貨郎擔(dān)問(wèn)題，是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。

假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。9.3求解旅行商問(wèn)題9.3.2采用蠻力法求解TSP問(wèn)題02136858587589367

以右圖所示的一個(gè)4城市圖為例，假設(shè)TSP問(wèn)題的起點(diǎn)為0，求出的所有從頂點(diǎn)0到頂點(diǎn)0并通過(guò)所有頂點(diǎn)的路徑如下：路徑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

【算法分析】對(duì)于圖中的n個(gè)頂點(diǎn)，求1～n-1全排列的時(shí)間為O(n×n!)，對(duì)于O(n!)的路徑，求每條路徑長(zhǎng)度的時(shí)間為O(n)，所以算法的時(shí)間復(fù)雜度為O(n×n!)。9.3.3采用動(dòng)態(tài)規(guī)劃求解TSP問(wèn)題

假設(shè)從頂點(diǎn)s（這里s=0）出發(fā)，令f(V，i)表示從頂點(diǎn)s出發(fā)經(jīng)過(guò)V（一個(gè)頂點(diǎn)的集合）中所有頂點(diǎn)有且僅有一次到達(dá)頂點(diǎn)i的最短路徑長(zhǎng)度。0siVf(V，i):0s0Vf(V，0):f(V，0)的結(jié)果就是最終結(jié)果當(dāng)V為空集，那么f(V，i)表示從頂點(diǎn)s不經(jīng)過(guò)任何頂點(diǎn)到達(dá)頂點(diǎn)i，顯然此時(shí)有f(V，i)=g.edges[s][i]。如果V不為空，對(duì)于jV，那么f(V-{j}，j)就是子問(wèn)題的最優(yōu)解。嘗試V中的每個(gè)頂點(diǎn)j，并求出最優(yōu)解：

f(V，i)=min{f(V-{j}，j)+g.edges[j][i]}0sjiV-{j]0siVmin0siV=?0sig.edges[s][i]對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移方程（s=0）如下：f(V，i)=g.edges[0][i] 當(dāng)V={}f(V，i)=min(f(V-{j}，j)+g.edges[j][i]|jV}

當(dāng)V≠{}f(V，0)的結(jié)果即為所求。

起點(diǎn)s=0，f({1，2，3}，0)就是從頂點(diǎn)0出發(fā)經(jīng)過(guò)頂點(diǎn)1、2、3到達(dá)頂點(diǎn)0的最短路徑長(zhǎng)度。

從f({1，2，3}，0)出發(fā)進(jìn)行遞推，達(dá)到葉子結(jié)點(diǎn)后進(jìn)行求值，求解結(jié)果為23，對(duì)應(yīng)的最短路徑是02310。02136858587589367采用STL的set<int>容器表示頂點(diǎn)集合V。對(duì)應(yīng)的遞歸求解程序如下：typedefset<int>SET;//采用set<int>表示頂點(diǎn)集合//問(wèn)題表示ints=0; //指定起點(diǎn)為0MGraphg; //圖的鄰接矩陣intf(SETV,inti) //求TSP所有解的路徑長(zhǎng)度{intminpathlen=INF; //最短路徑長(zhǎng)度if(V.size()==0) //當(dāng)V為空時(shí) returng.edges[0][i];else //當(dāng)V為不空時(shí){SET::iteratorit;for(it=V.begin();it!=V.end();++it) //掃描集合V中的頂點(diǎn)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] 當(dāng)V={}f(V，i)=min(f(V-{j}，j)+g.edges[j][i]|jV} 當(dāng)V≠{}

【算法分析】對(duì)于圖中的n個(gè)頂點(diǎn)，本算法需要對(duì){1，2，…，n-1}的每個(gè)子集都要操作，時(shí)間復(fù)雜度是O(2n)，當(dāng)n比較大時(shí)非常耗時(shí)的。9.3.4采用回溯法求解TSP問(wèn)題

用f(V，i)求從頂點(diǎn)i出發(fā)經(jīng)過(guò)V（它是一個(gè)頂點(diǎn)的集合）中各個(gè)頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)s的最短路徑長(zhǎng)度。minpath保存最短路徑，minpathlen保存最短路徑長(zhǎng)度，V用set<int>容器表示，初始時(shí)V={1，2，3}。

用path、pathlen表示當(dāng)前路徑和路徑長(zhǎng)度，采用的剪枝規(guī)則是：當(dāng)一個(gè)結(jié)點(diǎn)的當(dāng)前路徑長(zhǎng)度大于minpathlen，該結(jié)點(diǎn)變成死結(jié)點(diǎn)。采用回溯法求解TSP問(wèn)題的基本框架如下：f(V,i,path,pathlen){頂點(diǎn)i添加到path，求出pathlen;if(V為空){if(頂點(diǎn)i到起點(diǎn)s有邊)

得到一條路徑;

比較求minpath和minpathlen;}else{對(duì)于V中的每個(gè)頂點(diǎn)j;tmpV=V-{j};if(pathlen<minpathlen) //剪枝處理

f(tmpV,j,path,pathlen);}}02136858587589367typedefset<int>SET;//采用set<int>表示頂點(diǎn)集合//問(wèn)題表示ints; //指定起點(diǎn)MGraphg; //圖的鄰接矩陣//求解過(guò)程表示intCount=1; //路徑條數(shù)累計(jì)vector<int>minpath; //保存最短路徑intminpathlen=INF; //保存最短路徑長(zhǎng)度voidTSP(SETV,inti,vector<int>path,intpathlen){intprev;if(path.size()>0) //path不為空prev=path.back(); //prev為路徑上的最后一個(gè)頂點(diǎn)path.push_back(i); //添加當(dāng)前頂點(diǎn)ipathlen+=g.edges[prev][i]; //累計(jì)路徑長(zhǎng)度if(V.size()==0) //找到一個(gè)葉子結(jié)點(diǎn){if(g.edges[i][s]!=0&&g.edges[i][s]!=INF)

//頂點(diǎn)i到起點(diǎn)s有邊{path.push_back(0); //路徑中加入起點(diǎn)0pathlen+=g.edges[i][s]; //累計(jì)路徑長(zhǎng)度dispasolution(path,pathlen);//輸出一條路徑if(pathlen<minpathlen) //比較求最短路徑{minpathlen=pathlen;minpath=path;}}}else //對(duì)于非葉子結(jié)點(diǎn){SET::iteratorit;for(it=V.begin();it!=V.end();it++){SETtmpV=V;intj=*it; //選擇頂點(diǎn)jtmpV.erase(j); //從V中刪除頂點(diǎn)j得到tmpVif(pathlen<minpathlen) //剪枝TSP(tmpV,j,path,pathlen);//遞歸調(diào)用}}}

【算法分析】對(duì)于圖中的n個(gè)頂點(diǎn)，本算法需要對(duì){1，2，…，n-1}的每個(gè)子集都要操作，時(shí)間復(fù)雜度是O(2n)。9.3.5采用分枝限界法求解TSP問(wèn)題

采用優(yōu)先隊(duì)列式分枝限界法求解，用STL的priority_queue<NodeType>容器作為優(yōu)先隊(duì)列，其中NodeType的類型聲明如下：structNodeType

//隊(duì)列結(jié)點(diǎn)類型{intv; //當(dāng)前頂點(diǎn)intnum; //路徑中的結(jié)點(diǎn)個(gè)數(shù)vector<int>path; //當(dāng)前路徑intpathlen; //當(dāng)前路徑長(zhǎng)度intvisited[MAXV]; //頂點(diǎn)訪問(wèn)標(biāo)記booloperator<(constNodeType&s)const{returnpathlen>s.pathlen; //pathlen越小越優(yōu)先出隊(duì)}};

用結(jié)點(diǎn)e的（e.v，e.num，e.pathlen）表示狀態(tài)，對(duì)于圖9.16，起點(diǎn)s=0，采用分枝限界法求解的解空間如下圖所示，圖中陰影框表示最優(yōu)解結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)旁的數(shù)字表示結(jié)點(diǎn)出隊(duì)的順序，帶的結(jié)點(diǎn)表示死結(jié)點(diǎn)。02136858587589367//問(wèn)題表示ints; //指定起點(diǎn)MGraphg; //圖的鄰接矩陣//求解過(guò)程表示intCount=1; //路徑條數(shù)累計(jì)vector<int>minpath; //保存最短路徑intminpathlen=INF; //保存最短路徑長(zhǎng)度structNodeType //隊(duì)列結(jié)點(diǎn)類型voidTSP() //分枝限界法求起點(diǎn)為s的TSP問(wèn)題{NodeTypee,e1;priority_queue<NodeType>qu; //定義優(yōu)先隊(duì)列que.v=0; //建立起點(diǎn)s對(duì)應(yīng)的結(jié)點(diǎn)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); //根結(jié)點(diǎn)e進(jìn)隊(duì)while(!qu.empty()) //隊(duì)不空循環(huán){e=qu.top();qu.pop(); //出隊(duì)結(jié)點(diǎn)eif(e.num==g.n) //到達(dá)葉子結(jié)點(diǎn){ if(g.edges[e.v][s]!=0&&g.edges[e.v][s]!=INF)

//e.v到起點(diǎn)s有邊 {e.path.push_back(s); //路徑中加入起點(diǎn)s e.pathlen+=g.edges[e.v][s];

//另外計(jì)入從e.v到起點(diǎn)s的路徑長(zhǎng)度dispasolution(e.path,e.pathlen);if(e.pathlen<minpathlen) //比較求最短路徑{minpathlen=e.pathlen;minpath=e.path; } }}else //非葉子結(jié)點(diǎn){for(intj=1;j<g.n;j++) //j從頂點(diǎn)1到n-1循環(huán){if(g.edges[e.v][j]!=0&&g.edges[e.v][j]!=INF)

//當(dāng)前頂點(diǎn)到頂點(diǎn)j有邊{if(e.visited[j]==1) //跳過(guò)路徑中重復(fù)的頂點(diǎn)jcontinue;e1.v=j; //建立e.v的相鄰頂點(diǎn)j對(duì)應(yīng)的結(jié)點(diǎn)e1e1.num=e.num+1;e1.path=e.path;e1.path.push_back(j); //path添加頂點(diǎn)je1.pathlen=e.pathlen+g.edges[e.v][j];for(inti=0;i<g.n;i++) //復(fù)制visitede1.visited[i]=e.visited[i];if(e1.pathlen<minpathlen) //剪枝{e1.visited[j]=1;qu.push(e1);}}}}}}

【算法分析】對(duì)于圖中的n個(gè)頂點(diǎn)，上述算法的時(shí)間復(fù)雜度為O(2n)。9.3.6采用貪心法求解TSP問(wèn)題實(shí)際上TSP問(wèn)題不滿足貪心法的最優(yōu)子結(jié)構(gòu)性質(zhì)，所以采用貪心法不一定得到最優(yōu)解，但可以采用合理的貪心策略。如可以采用最近鄰點(diǎn)策略，即從任意城市出發(fā)，每次在沒(méi)有到過(guò)的城市中選擇最近的一個(gè)，直到經(jīng)過(guò)了所有的城市，最后回到出發(fā)城市。頂點(diǎn)0～頂點(diǎn)00182533619351706求出最短路徑為：

0→2→3→1→0時(shí)間復(fù)雜度為O(n2)02136858587589367

實(shí)際上TSP問(wèn)題不滿足貪心法的最優(yōu)子結(jié)構(gòu)性質(zhì)，所以采用貪心法不一定得到最優(yōu)解，但可以采用合理的貪心策略。局部最優(yōu)全局最優(yōu)==?貪心法需要證明具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。9.4.1相關(guān)概念

設(shè)帶權(quán)有向圖G=(V,E)表示一個(gè)網(wǎng)絡(luò)，其中兩個(gè)分別稱為起點(diǎn)s和終點(diǎn)t的頂點(diǎn)，起點(diǎn)的入度為零，終點(diǎn)的出度為零，其余頂點(diǎn)稱為中間點(diǎn)，有向邊<u,v>上的權(quán)值cu,v表示從頂點(diǎn)u到v的容量。

下圖就是一個(gè)網(wǎng)絡(luò)，邊上的數(shù)值表示容量。9.4網(wǎng)絡(luò)流012453614108533867463

定義在邊集合E上的一個(gè)函數(shù)f(u，v)為網(wǎng)絡(luò)G上的一個(gè)流量函數(shù)（flowfunction），滿足以下條件：容量限制（capacityconstraints）：V中的任意兩個(gè)頂點(diǎn)u、v，滿足f(u，v)≤c(u，v)，即一條邊的流量不能超過(guò)它的容量。

斜對(duì)稱（skewsymmetry）：V中的任意兩個(gè)頂點(diǎn)u、v，滿足f(u，v)=-f(v，u)。即u到v的流量必須是v到u的流量的相反值。流守恒（flowconservation）：V中的非s、t其他任意兩個(gè)頂點(diǎn)u、v，滿足，即頂點(diǎn)的凈流量（出去的總流量減去進(jìn)來(lái)的總流量）是零。滿足上述條件的流量函數(shù)稱為網(wǎng)絡(luò)流（network-flows），簡(jiǎn)稱為流。012453614108533867463012453614,1010,38,65,33,33,08,76,67,74,16,63,1f為網(wǎng)絡(luò)流一個(gè)網(wǎng)絡(luò)

由于流過(guò)網(wǎng)絡(luò)的流量具有一定的方向，邊的方向就是流量流過(guò)的方向，每一條邊上的流量應(yīng)小于其容量，中間點(diǎn)的流入量總和等于其流出量總和，對(duì)于起點(diǎn)和終點(diǎn)，總輸出流量等于總輸入流量。滿足這些條件的流f稱為可行流，可行流總是存在的。012453614,1010,38,65,33,33,08,76,67,74,16,63,1

如果所有的邊的流量均取0，即對(duì)于所有的頂點(diǎn)u、v，f(u，v)=0，稱此可行流為零流（zeroflow），這樣的零流一定是可行流。

如果某一條邊的流量f(u，v)=c(u，v)，則稱流f(u，v)是飽和流，否則為非飽和流。f(u，v)>0的邊稱為非零流邊。

最大網(wǎng)絡(luò)流問(wèn)題就是求一個(gè)這樣的可行流f，其流量達(dá)到最大。012453614,1010,38,65,33,33,08,76,67,74,16,63,1流f的值定義為|f|=，即從起點(diǎn)s出發(fā)的總流（這里記號(hào)|·|表示流的值，并表示絕對(duì)值）。

在最大流問(wèn)題中，給出一個(gè)具有起點(diǎn)s和終點(diǎn)t的網(wǎng)絡(luò)G，從中找出從s到t的最大值流。

給定一個(gè)網(wǎng)絡(luò)G=(V，E)，其流量函數(shù)為f，由f對(duì)應(yīng)的殘留網(wǎng)絡(luò)或者剩余網(wǎng)絡(luò)Gf=(V，Ef)，Gf中的邊稱為殘留邊：

若G中有邊<u，v>且f(u，v)<c(u，v)，則對(duì)應(yīng)的殘留邊<u，v>的流量=c(u，v)-f(u，v)（表示從頂點(diǎn)u到v可以增加的最大額外網(wǎng)絡(luò)流量），若G中有邊<u，v>且f(u，v)>0，則對(duì)應(yīng)的殘留邊<v，u>的流量=f(u，v)（表示從頂點(diǎn)u到v可以減少的最大額外網(wǎng)絡(luò)流量）。012453614,1010,38,65,33,33,08,76,67,74,16,63,1012453647262767362103331113

若f是G中的一個(gè)流，Gf是由G導(dǎo)出的殘留網(wǎng)絡(luò)，f'是Gf中的一個(gè)流，則f+f'是G中一個(gè)流，且其值|f+f'|=|f|+|f'|。

設(shè)μ是網(wǎng)絡(luò)G中的一條從頂點(diǎn)u到頂點(diǎn)v的一條路徑，在路徑中與路徑的方向一致的邊稱為前向邊（為可以增加流量的邊），其集合記為μ+；

在路徑中與路徑的方向相反的邊稱