算法與數(shù)據(jù)結(jié)構(gòu)

1

第十九講最短路徑12教材與參考資料普通高等教育“十一五”國家級規(guī)劃教材普通高等教育精品教材《算法與數(shù)據(jù)結(jié)構(gòu)—C語言描述》（第2版）張乃孝編著,高等教育出版社2008.第9章圖（9.5）普通高等教育“十一五”國家級規(guī)劃教材配套參考書《算法與數(shù)據(jù)結(jié)構(gòu)》（第2版）學(xué)習(xí)指導(dǎo)與習(xí)題解析張乃孝編著,高等教育出版社2009.239.5最短路徑如果圖中從一個頂點可以到達(dá)另一個頂點，則稱這兩個頂點間存在一條路徑。從一個頂點到另一個頂點間可能存在多條路徑，而每條路徑上經(jīng)過的邊數(shù)并不一定相同。如果圖是一個帶權(quán)圖，則路徑長度為路徑上各邊的權(quán)值的總和，兩個頂點間路徑長度最短的那條路徑稱為兩個頂點間的最短路徑，其路徑長度稱為最短路徑長度。49.5.1Dijkstra算法Dijkstra算法求解從頂點v0出發(fā)到其它各頂點最短路徑。該算法假設(shè)所有邊的權(quán)都大于等于零。5基本思想設(shè)置一個集合U，存放已求出最短路徑的頂點，V-U是尚未確定最短路徑的頂點集合。U的初始狀態(tài)為{v0}。按路徑長度遞增的次序逐個產(chǎn)生vx的最短路徑,把vx加入U中。直到U=V時終止。距離值V-U圖GUv0vi1vi3vi2為每個頂點設(shè)置一個距離值（已知最短距離）：集合U中某頂點的距離值就是從頂點v0到該頂點的最短路徑長度；集合V-U中某頂點的距離值是從頂點v0到該頂點的只包括集合U中頂點為中間頂點的最短路徑長度。性質(zhì)：若vi是V-U中距離值最小的結(jié)點，那么這個距離值就是從v0到vi的最短路徑。。67初始狀態(tài)：集合U中只有頂點v0，頂點v0對應(yīng)的距離值為0，集合V-U中頂點vi的距離值為邊(v0,vi)(i=1,2,…,n-1)的權(quán)，如果v0和vi間無邊直接相連，則vi的距離值為∞（實際程序中可以用一個足夠大的數(shù)代替）。處理框架：（1）在集合V-U中選擇距離值最小的頂點vmin加入集合U；（2）對集合V-U中各頂點的距離值進(jìn)行修正：如果加入頂點vmin為中間頂點后，使v0到vi的距離值比原來的距離值更小，則修改vi的距離值。（3）重復(fù)（1）（2）操作，直到從v0出發(fā)可以到達(dá)的所有頂點都在集合U中為止。按路徑長度遞增的次序逐個產(chǎn)生最短路徑例：已知帶權(quán)圖G10如下圖所示及其鄰接矩陣A，求從頂點v0到其它各頂點的最短路徑úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥=03030350201502051504510500A45v050v15v41520v215v33v53520301045v050v15v41520v215v33v535203010[45][50][10][￥][￥]綠色為從U到V-U的邊，選(v0,v2)把v2加入U845v050v15v41520v215v33v535203010[￥][45][25][50]選(v2,v3)，把v3加入U45v050v15v41520v215v33v535203010[45][45][￥]選(v3,v1)，把v1加入U45v050v15v41520v215v33v535203010[￥][45]選(v0,v4)，把v4加入U45v050v15v41520v215v33v535203010910圖選擇鄰接矩陣表示法，其中關(guān)系矩陣的對角線初值均取0。算法中，將放入集合Ｕ中結(jié)點對應(yīng)的關(guān)系矩陣中對角線元素值修改為1；另外設(shè)置一個數(shù)組dist，dist[ｉ]用于存放v0到頂點vｉ的最短路徑及其最短路徑長度（計算過程中為距離值）∶

ypedefstruct{ AdjTypelength; /*最短路徑長度*/ intprevex; /*從v0到達(dá)vi(i=1,2,…n-1)的最短路徑上vi的前趨頂點*/}Path;Path*dist;存儲結(jié)構(gòu)11修正距離值方法的精化在加入頂點vmin為中間頂點后，如果dist[i].length>dist[min].length+G.arcs[min][i]，則將頂點vi的距離值改為：dist[min].length+G.arcs[min][i]并修改路徑上vi的前趨頂點：dist[i].prevex=min。

12①．初始時，集合U中只有頂點v0。結(jié)果dist[n]為{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}②．在集合V-U中找出距離值最小的頂點v2，將頂點v2加入集合U中。結(jié)果dist[n]為{{0,0},{50,0},{10,0},{MAX,-1},{45,0},{MAX,-1}}③．按min=2調(diào)整集合V-U中頂點的距離值。因為dist[1].legth=50，dist[2].length+graph.arcs[2][1]=10+MAX，因此，頂點v1的距離值不需要調(diào)整。因為dist[3].length=MAX，dist[2].length+graph.arcs[2][3]=10+15=25，因此，頂點v3的距離值調(diào)整為25，其前趨頂點為v2。同理，頂點v4，v5的距離值不需要調(diào)整。結(jié)果dist[n]為{{0,0},{50,0},{10,0},{25,2},{45,0},{MAX,-1}}在數(shù)組dist上模擬算法13④．同理在集合V-U中找出當(dāng)前距離值最小的頂點v3，并調(diào)整集合V-U中頂點的距離值。結(jié)果dist[n]為{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑤．在集合V-U中找出當(dāng)前距離值最小的頂點v1。并調(diào)整集合V-U中頂點的距離值。結(jié)果dist[n]為{{0,0},

{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑥．在集合V-U中找出當(dāng)前距離值最小的頂點v4。并調(diào)整集合V-U中頂點的距離值。結(jié)果dist[n]為{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}⑦．沒有可以再加入集合U的頂點了，說明從頂點v0到頂點v5之間無路徑相通。過程結(jié)束。在數(shù)組dist上模擬算法（續(xù)）14

由數(shù)組dist的prevex字段得到頂點v0到各頂點的最短路徑{{0,0},{45,3},{10,0},{25,2},{45,0},{MAX,-1}}如從v0到v1的最短路徑，dist[1].prevex=3可知路徑上頂點v1的前一個頂點是v3，dist[3].prevex=2可知路徑上頂點v3的前一個頂點是v2，dist[2].prevex=0可知路徑上前一個頂點是v0，即最短路徑為(v0,v2,v3,v1)。voidinit(GraphMatrix*pgraph,Pathdist[]){inti;dist[0].length=0;dist[0].prevex=0;pgraph->arcs[0][0]=1;/*用矩陣對角線元素記錄集合U，為1表示在U中。*/for(i=1;i<pgraph->n;++i){/*初始化V-U中頂點的距離值*/

dist[i].length=pgraph->arcs[0][i];if(dist[i].length!=MAX)dist[i].prevex=0;elsedist[i].prevex=-1;}}15初始化dist[]voiddijkstra(GraphMatrix*graph,Pathdist[]){inti,j,mv,n=graph->n;AdjTypeminw;init(graph,dist);/*初始化，集合U中只有頂點v0*/for(i=1;i<n;++i){minw=MAX;mv=0;

for(j=1;j<n;++j)/*在V-U中選出距v0最近的頂點*/if(graph->arcs[j][j]==0&&dist[j].length<minw){mv=j;minw=dist[j].len;}if(mv==0)break;/*v0與V-U的頂點不連通，結(jié)束*/graph->arcs[mv][mv]=1;/*頂點mv加入U*/for(j=1;j<n;++j){/*調(diào)整V-U頂點的已知最短路徑*/if(graph->arcs[j][j]==0&&/*為V-U的頂點*/dist[j].length>dist[mv].length+graph->arcs[mv][j]){dist[j].prevex=mv;/*調(diào)整已知最短路徑信息*/dist[j].length=dist[mv].length+graph->arcs[mv][j];}}}}16Dijkstra算法17算法分析算法中的初始化部分的時間復(fù)雜度為O(n)，求最短路徑部分由一個大循環(huán)組成，其中外循環(huán)運行n-1次，內(nèi)循環(huán)為兩個，均運行n-1次，因此，算法的時間復(fù)雜度為O(n2)。另外需要注意，在算法中改變了關(guān)系矩陣中的初始狀態(tài)，如果要求算法不能破壞原始數(shù)據(jù)，就需要另外增加數(shù)據(jù)結(jié)構(gòu)記錄Ｕ集合的值?？臻g代價是Ｏ（ｎ）．189.5.2Floyd算法功能：求帶權(quán)圖每一對頂點間的最短路徑基本思想：圖采用鄰接矩陣作為存儲結(jié)構(gòu)。把關(guān)系矩陣看成是沒有經(jīng)過任何中間結(jié)點，直接可以到達(dá)的每一對頂點間的最短路徑。然后按結(jié)點在結(jié)點表中的順序，每次考慮增加一個新的結(jié)點，在允許這個結(jié)點作為中間結(jié)點的條件下，計算每一對頂點間的最短路徑的縮短變化。直到把所有結(jié)點都考慮進(jìn)去為止，結(jié)果得到每一對頂點間的最短路徑。19數(shù)據(jù)結(jié)構(gòu)

為了在算法中不破壞原始的關(guān)系矩陣，需要定義一個與關(guān)系矩陣同樣大小，以關(guān)系矩陣作為其初始狀態(tài)的矩陣，用于存放處理中每對頂點間的距離值（或最短路徑長度）。為了保存全部最短路徑的軌跡，需要另外設(shè)計一個與關(guān)系矩陣同樣大小的整數(shù)矩陣，存放vi到vj最短路徑上vi的后繼頂點的下標(biāo)值。把它們封裝在下面定義的結(jié)構(gòu)類型ShortPath中：

typedefstruct{ AdjType*a[];/*存放每對頂點間最短路徑長度*/ int*nextvex[];/*存放vi到vj最短路徑上vi的后繼頂點的下標(biāo)值*/}ShortPath;voidFloyd(GraphMatrix*pgraph,ShortPath*ppath){inti,j,k,n=pgraph->n;for(i=0;i<n;++i)for(j=0;j<n;++j){if(pgraph->arcs[i][j]!=MAX)ppath->nextvex[i][j]=j;elseppath->nextvex[i][j]=-1;ppath->a[i][j]=pgraph->arcs[i][j];/*復(fù)制鄰接矩陣*/}for(k=0;k<n;++k)for(i=0;i<n;++i)for(j=0;j<n;++j){if(ppath->a[i][k]==MAX||ppath->a[k][j]==MAX)continue;if(ppath->a[i][j]>ppath->a[i][k]+ppath->a[k][j]){ppath->a[i][j]=ppath->a[i][k]+ppath->a[k][j];ppath->nextvex[i][j]=ppath->nextvex[i][k];}

}}20Floyd算法21代價分析算法中初始化部分由一個兩重循環(huán)組成，其中外循環(huán)運行n次，內(nèi)循環(huán)也運行n次，初始化部分的時間復(fù)雜度為O(n2)。迭代生成最短路徑長度矩陣A和路徑矩陣nextvex的部分為三重循環(huán)的嵌套，其時間復(fù)雜度為O(n3)。Floyd算法的時間復(fù)雜度為O(n3)。

空間代價是Ｏ（ｎ2）（比較大）。22例題用Floyd方法求圖G10各頂點間的最短路徑長度。23初始狀態(tài)24加入V025加入V126加入V227加入V328例如，想知道v0到v1的最短路徑：由A[0][1]可知v0到v1的最短路徑長度為45，路徑由nextvex[0][1]=2可知頂點v0的下一頂點為v2，由nextvex[2][1]=3可知v2的下一頂點為v3，由nextvex[3][1]=1可知v3的下一頂點為v1，因此從v0到v1的最短路徑為v0→v2→v3→v1路徑的查找29本講重點：圖中從一個頂點到另一個頂點間路徑長度最短的路徑稱為兩個頂點間的最短路徑。本章介紹了從頂點v0出發(fā)到其它頂點最短路徑的Dijkstra算法和求每一對頂點間的最短路徑的Floyd算法。討論：動態(tài)規(guī)劃算法*有些問題在分解時會產(chǎn)生大量的子問題，同時分得的子問題界限不清，互相交叉，因而在解這類問題時，將可能重復(fù)多次解同一個子問題。解決的方法可以在解決每個子問題后把它的解（包括其子子問題的解）保留在一個表格中，若遇到求與之相同的子問題的解時，就可以從表中把解找出來直接使用。本書所見過的運用動態(tài)規(guī)劃法的算法有：所有結(jié)點間的最短路徑算法（算法９．７）及最佳二叉排序樹的構(gòu)造算法（算法７．５）。30給定排序的關(guān)鍵碼集合{key1,key2,…,keyn}和兩個權(quán)集合{p1,…,pn}和{q0,q1…,qn},其中pi是檢索內(nèi)部結(jié)點i的概率,

qj是被檢索關(guān)鍵碼屬于外部結(jié)點j的關(guān)鍵碼集合的概率.問題

:要求構(gòu)造一棵最佳二叉排序樹,即構(gòu)造出一棵二叉排序樹,使下面的函數(shù)達(dá)到最小(E(n)一定也達(dá)到最小)：上式稱為包含n個內(nèi)部結(jié)點和n+1個外部結(jié)點的二叉排序樹的花費,記作C(0,n).性質(zhì)：最佳二叉排序樹里的任何子樹都最佳.31回顧：不等概率的最佳二叉排序樹的構(gòu)造花費的計算在構(gòu)造T(i,j)時,對所有i<k≤j,

T(i,k-1)和T(k,j)都已存在,而且已知相應(yīng)花費C(i,k)和C(k,j).對每個k,以keyk

為根,

T(i,k-1)和T(k,j)為左右子樹的二叉樹的花費為:

Ck(i,j)=W(i,j)+C(i,k-1)+C(k,j)

(結(jié)點增加一層).從所有可能k中選擇使Ck(i,j)達(dá)到最小的那個k,與之對應(yīng)樹就是T(i,j),其根R(i,j)=k.新樹的代價可以由構(gòu)造它的已知最佳二叉排序樹的代價算出：C(i,j)=W(i,j)+minikj(C(i,k-1)+C(k,j)).NOTE:T(i,i)為不包含任何內(nèi)部結(jié)點,僅僅由權(quán)值為qi的外部結(jié)點構(gòu)成,C(i,i)=0.32數(shù)組p存放內(nèi)部結(jié)點的權(quán)(p[1],…,p[n])；數(shù)組q存放外部結(jié)點的權(quán)(q[0],…,q[n])；c[i][j]保存T(i,j)的花費;w[i][j]保存T(i,j)的權(quán);r[i][j]保存T(i,j)的根.構(gòu)造好的最佳二叉排序樹的總花費存放在c[0][n]；r[0][n]是根結(jié)點的編號。根據(jù)r[0][n]的值，就可以確定兩棵子二叉樹的根在那里：33數(shù)據(jù)的存儲w: 4121417 0358 0014 0001直接算出r: 0100 0020 0003 0000c: 01200 0050 0004 0000第一步r: 0110 0022 0003 0000c: 012190 00512 0004 0000第二步r: 0111 0022 0003 0000c: 0121929 00512 0004 0000第三步計算結(jié)果:34P:{5,1,2}Q:{4,3,1,1}C(i,j)=W(i,j)+minikj(C(i,k-1)+C(k,j)).

1，求著色問題近似解的貪心法。

2，構(gòu)造最小生成樹的prim算法（算法９．5）。這里的條件是所有權(quán)都是正數(shù)，在遇到帶有負(fù)權(quán)邊的圖時，這樣做就可能產(chǎn)生錯誤的結(jié)果。

3，Ｄｉｊｋｓｔｒａ的最短路徑算法（算法９．６）求從源點到其他各結(jié)點的最短路徑。這里的條件是所有權(quán)都是正數(shù)，在遇到帶有負(fù)權(quán)邊的圖時，這樣做就可能產(chǎn)生錯誤的結(jié)果。

35貪心法動態(tài)規(guī)劃法與貪心法的相同點兩者的相同點是