最短路徑學(xué)年論文

--#-第一次迭代計(jì)算T(v),j=2,3,4,5,6如下{?0+5}=5T(v)=min{f(v),W(v{?0+5}=52112T(v)=min存(v),W(v)+w}=min{a,0+2}=2TOC\o"1-5"\h\z3113T(v)=minkr(v),W(v)+w}=min{a,0+a}=a4114T(v)=a,T(v)=a6②取minj{T(v)}=2=T(v)，令W(v)=T(v)②取minjj333③由于k=3H(n=6),令S=S，v,V,V},i=3轉(zhuǎn)⑴第二次迭代:①算T(v),j=2,4,5,6如下jT(v)=min{T(v),W(v)+w}=min{5,2+1}=3TOC\o"1-5"\h\z22323T(v)=min{T(v),W(v)+w}=min{8,2+8}=84334T(v)=min{T(v),W(v)+w}=min{10,2+10}=105335T(v)=min{T(v),W(v)+w}=min{a,2+a}=a6336取min{T(v)}=3=T(v)令W(v)=T(v)=3_j222vesj由于k=2H(n=6),令s={v,v,v}i=2轉(zhuǎn)⑴456第三次迭代:算T(v),j=4,5,6如下jT(v)=min{T(v),W(v)+w}=min{8,3+5}=8TOC\o"1-5"\h\z4224T(v)=min{T(v),W(v)+w}=min{10,3+9}=105225T(v)=a6取min{T(v)}=8=T(v),W(v)=T(v)=8_j444vesj

③由于k=4工(n=6),令S={v,v}i=4轉(zhuǎn)⑴56第四次迭代:①算T(v),j=5,6如下jT(v)=min{T(v),W(v)+w}=min{10,2+8}=10TOC\o"1-5"\h\z5445{?8+5}=13T(v)=min{T(v),W(v)+w}{?8+5}=13②取min{T(②取min{T(v)}=j10=T(v),W(v)=T(v)=10555vesj③由于k=5工(n=6),令s={v}轉(zhuǎn)⑴第五次迭代:①算T(v),j=6如下jT(v)=min{T(v),W(v)+w}=min{13,10+2}=1266556②由于k=6=n。因此已找到v到v的最短距離為12。計(jì)算結(jié)束。16對應(yīng)的迭代表格如下：迭代suv2v3v4v5v61{1}——5（2）ggg2{1,3}v3（3）21012g3{1,3,2}v232（8）12g4{1,3,2,4}v4328（12）155{1,3,2,4}v532812（12）找最短路線:逆向追蹤得vTvTvTvTvTv132456最短距離為12,即從城市v到城市v的距離最短,即費(fèi)用最省。163.3算法的正確性和計(jì)算復(fù)雜性3.3.1貪心選擇性質(zhì)Dijkstra算法是貪心算法策略的一個(gè)典型例子。它所做的貪心選擇是從V—S中選擇具有最短特殊路徑的頂點(diǎn)u從而確定從源到u的最短路徑長度dist[u]。這種貪心選擇導(dǎo)致最優(yōu)解在于如果存在一條源到U且長度比dist[u]更短的路，設(shè)這條路初次走出S之外到達(dá)的頂點(diǎn)xgV—S，然后徘徊于S內(nèi)外若干次，最后離開S到達(dá)u,如圖2所示。在這條路徑上，分別標(biāo)記d(v,x)，d(x,u)和d(v,u)為頂點(diǎn)v到頂點(diǎn)x,頂點(diǎn)x到頂點(diǎn)u和頂點(diǎn)v到頂點(diǎn)u的路長，那么有：dist[x]<d(v,x)d(v,x)+d(x,u)=d(v,u)<dist[u]利用權(quán)邊的非負(fù)性，可知d(v,x)>0，從而推出dist[x]<dist[u]。此為矛盾。這就證明了dist[u]是從源點(diǎn)到u的最短路徑長度。3.3.2最優(yōu)子結(jié)構(gòu)性質(zhì)要完成Dijkstra算法正確性的證明，還必須證明最優(yōu)子結(jié)構(gòu)性質(zhì)，即算法中確定的dist[u]確實(shí)是當(dāng)前從源到頂點(diǎn)u的最短特殊路徑長度。為此，只要考察算法在添加u到S中后，dist[u]的值所起的變化。將添加u之前的S成為老S。當(dāng)添加了u之后，可能出現(xiàn)一條到頂點(diǎn)i的新的特殊路。如果這條新特殊路是先經(jīng)過老S到達(dá)頂點(diǎn)u,然后從u經(jīng)一條邊直接到達(dá)頂點(diǎn)i，則這種路的最短的長度是dist[u]+c[u][i]。此時(shí)如果dist[u]+c[u][i]vdist[i],貝y計(jì)算中用dist[u]+c[u][i]作為dist[i]的新值。如果這條新特殊路徑經(jīng)過老S到達(dá)u后，不是從u經(jīng)過一條邊直接到達(dá)i,而是像圖3那樣，回到老S中某個(gè)頂點(diǎn)x,最后才到達(dá)頂點(diǎn)i,那么由于x在老S中，因此x比u先加入S,所以圖3中從源到x的路的長度比從源到u,再從u到x的路的長度小。于是當(dāng)前dist[i]的值小于從源經(jīng)x到i的路的長度，也小于圖中從源經(jīng)u和x,最后到達(dá)i的路的長度。因此，在計(jì)算中不必考慮這種路。由此可知，不論算法中dist[u]的值是否發(fā)生變化，它總是關(guān)于當(dāng)前頂點(diǎn)集S到達(dá)u的最短特殊路徑長度。圖3非最短路徑的特殊路徑3.3.3計(jì)算復(fù)雜性對于一個(gè)具有n個(gè)頂點(diǎn)和e條帶權(quán)邊的圖來說，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要O(n)的時(shí)間。這個(gè)循環(huán)體需要執(zhí)行n-1次，所以完成循環(huán)需要O(n2)時(shí)間。算法的其余部分所需要的時(shí)間不超過O(n2)。Floyd算法Floyd算法描述Floyd算法又稱距離矩陣法，算法主要是尋找加權(quán)圖中任意兩個(gè)結(jié)點(diǎn)間最短路徑的算法。其基本思想是：兩結(jié)點(diǎn)間的最短路徑要么是相鄰時(shí)最短，要么是以通過幾個(gè)中間結(jié)點(diǎn)為跳板時(shí)距離最短。算法每次以其中一個(gè)結(jié)點(diǎn)為跳板，如果以該結(jié)點(diǎn)為跳板后兩結(jié)點(diǎn)間路徑縮短，則更新這兩結(jié)點(diǎn)間的路徑。算法執(zhí)行n次結(jié)束，直到測試完每個(gè)充當(dāng)跳板的結(jié)點(diǎn)。若用Dijkstra算法計(jì)算任意兩點(diǎn)間的最短路徑，需要執(zhí)行n次，且圖中含有負(fù)權(quán)值時(shí)不能用Dijkstra算法°Floyd算法只能求出兩點(diǎn)間最短路徑的長度，無法得到這條最短路徑,當(dāng)然，如果記錄了每步更新所經(jīng)過的中間結(jié)點(diǎn)，仍可通過回溯得到兩點(diǎn)間的最短路徑。Floyd算法步驟對于圖G，如果w(i,j)表示i和j之間的可實(shí)現(xiàn)的距離，那么w(i,j)表示端i和j之間的最短距離當(dāng)且僅當(dāng)對于任意的i,j,k，有w(i,j)<w(i,k)+w(k,j)。該算法用矩陣形式來表示，并進(jìn)行系統(tǒng)化的計(jì)算，通過迭代來消除不滿足上述定理的情況，對于n個(gè)端，一給定邊長d..的圖，順序計(jì)算各個(gè)nxn的W陣和R陣，前者代表徑長,后者代表轉(zhuǎn)接路由。ij其步驟如下：F:置W(0)=[W(0)]0ijij其中w0ij其中w0ijdij=Vg0v,v有邊ijv,v無邊ij和Ro=[r(o)]ij其中1j其中1jW(0)<gr(o)=Vijw(o)=g或i=jijIoij牛已得W和R(i陣’求叫和R(k)陣中的元素如下w(k)=min[w(k-1),w(k-1)+w(k-1)]ijijikkjIr(k-1),右如(k)=w(k-1)

rk=Vijijij

ijIr(k-1),右wk<w(k-1)

ikijijF:k<n，重復(fù)F；k=n，終止。21由上述步驟可見，W(k-1)TW(k)是計(jì)算經(jīng)v轉(zhuǎn)接時(shí)是否能縮短經(jīng)常，如有縮短，更k改w..并在R陣中記下轉(zhuǎn)接的端。最后算得W(n)和R(n)，就得到了最短徑長和轉(zhuǎn)接路由。ijFloyd算法實(shí)例假設(shè)某旅游路線的賦權(quán)圖如下:現(xiàn)在我們以上述生成的圖4為考察對象，根據(jù)算法流程，設(shè)W陣和R陣分別代表路徑長04ggg1g4014ggg4g1409ggggg909g12ggg90661ggg601g4g12610和轉(zhuǎn)接路由。那么計(jì)算結(jié)果如下：W(0)=「020006010300070204000R(0)=003050700040671000507020456004ggg1g4014gg(5)4g1409ggggg909g12ggg90661(5)gg601g4g12610W⑴=02000600204000R⑴=0030507000406710300(1)71(1)005070204560「04(18)gg1(8)4014gg54(18)1409g(19)(18)W(2)=gg909g12ggg906615(19)g601_(8)4(18)12610「02(2)006(2)1030017(2)2040(2)(2)R(2)=0030507000406711(2)0507_(2)2(2)4560「0418(27)g184014(23)g54181409g1918W(3)=(27)(23)909(28)12ggg90661519(28)601841812610「022(3)062103(3)0172204022R(3)=(3)(3)305(3)70004067112(3)5072224560-041827(36)18401423(32)54181409(18)1918W⑷=27239092812(36)(32)(18)9066151928601841812610-0223(4)621033(4)172204(4)22R(4)=3330537(4)(4)(4)406711235072224560-0418401418140W(5)=272393632181519_8418273618_233254918191809(15)129066(15)60112610_-022346210334172204422R(5)=33305(5)74444067112(5)5072224560-0418(16)(7)1(2)4014(20)(11)54181409181918W(6)=(16)(20)9091512(7)(11)189066151915601_(2)41812610-022(6)(6)6(6)103(6)(6)172204422R(6)=(6)(6)30557(6)(6)440671125507_(6)224560-0418(14)712--022(7)6664014(16)(10)54103(7)(7)171814091819182204422W(7)=(14)(16)909(13)12R(7)=(7)(7)305(7)77(10)1890666(7)440671519(13)601112(7)5072418126106224560經(jīng)過7輪迭代，我們得到了最終的W和R陣，分別包含了徑長信息和路由信息。我們可以從W（7）和R（7）中找到任何兩個(gè)端點(diǎn)間的最短徑長和最短路由，對應(yīng)著我們所建立的旅行線路模型中的任何兩景點(diǎn)間的最短路徑長度和路線。若要求旅游點(diǎn)3到點(diǎn)1的最短路徑，則可以從M⑺中找到對應(yīng)的最小值為18,從R（7）中找到r31=2，就是要經(jīng)點(diǎn)2轉(zhuǎn)接；再看鼻廣1，此時(shí)已經(jīng)到達(dá)目的節(jié)點(diǎn)，所以路由是點(diǎn)3—>點(diǎn)2—>點(diǎn)1。Dijkstra算法和Floyd算法在求最短路徑的異同相同：是按路徑長度遞增的思路進(jìn)行查找最短路徑。都需要借助帶權(quán)領(lǐng)接矩陣；都引進(jìn)了輔助數(shù)組；Floyd法的替代算法是n次調(diào)用Dijkstra法（n為圖G中結(jié)點(diǎn)數(shù)目）。相異：Dijkstra算法是從一點(diǎn)出發(fā)到其余路徑的最短路徑，而Floyd算法是找圖中所有頂點(diǎn)間的最短路徑；Dijkstra算法是找到最短后再嘗試?yán)迷撟疃梯o助找其余最短的；而Floyd算法是在插入第i-1個(gè)頂點(diǎn)的基礎(chǔ)上比較插入第i個(gè)后和之前的最短；路徑長度遞增不一樣：Dijkstra算法增的路徑是比較出最短的增，而Floyd算法增的路徑是按編號遞增；Dijkstra算法從源點(diǎn)出發(fā)，而弗法可以從任意點(diǎn)出發(fā)；⑤結(jié)果不同，Dijkstra算法找到的是從源點(diǎn)到其余頂點(diǎn)的最短路徑；Floyd算法則可以求任兩點(diǎn)之間的最短路徑。6利用計(jì)算機(jī)程序模擬算法對于圖G來說，如果G中的結(jié)點(diǎn)個(gè)數(shù)較少，可以通過逐步迭代或者通過以上的列表形式算出不同點(diǎn)之間的最短路徑，但相對于結(jié)點(diǎn)數(shù)目較多的圖而言，顯得力不從心，也大大增加了計(jì)算過程中的失誤率。這個(gè)時(shí)候，我們就迫切希望尋求算學(xué)工具來解決人工的局限性。為此引入Matlab來簡化求解步驟，通過輸入鄰接矩陣和始末點(diǎn)來快速計(jì)算最短路徑的值，并導(dǎo)出途經(jīng)各結(jié)點(diǎn)。其中Dijkstra算法中的例子，可以另vi~v6對應(yīng)于標(biāo)號1?6，鄰接矩陣為A,通過調(diào)用Matlab功能函數(shù)可迅速得出最優(yōu)路徑及相關(guān)途經(jīng)點(diǎn)。程序見附錄。7附錄Dijkstra算法：function[d,path]=dijkstra(W,s,t)[n,m]=size(W);ix=(W==0);W(ix)=inf;ifn~=m,error('SquareWrequired');endvisited(1:n)=0;dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;fori=1:(n-1),ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix);[a,u]=min(vec);visited(u)=1;forv=1:n,if(W(u,v)+dist(u)<dist(v)),dist(v)=dist(u)+W(u,v);parent(v)=u;end;end;endifparent(t)~=0,path=t;d=dist(t);whilet~=s,p=parent(t);path=[ppath];t=p;end;endFloyd算法：function[d,r]=floyd(a)n=size(a,1);d=a;fori=1:nforj=1:nr(i,j)=j;endendrfork=1:nfori=1:nforj=1:nifd(i,k)+d(k,j)d(i,j