貪心法求解單元最短路徑問(wèn)題

1、實(shí)驗(yàn)1貪心法求解單源最短路徑問(wèn)題實(shí)驗(yàn)內(nèi)容本實(shí)驗(yàn)要求基于算法設(shè)計(jì)與分析的一般過(guò)程（即待求解問(wèn)題的描述、算法設(shè)計(jì)、算法描述、算法正確性證明、算法分析、算法實(shí)現(xiàn)與測(cè)試）。應(yīng)用貪心策略求解有向帶權(quán)圖的單源最短路徑問(wèn)題。實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)本次實(shí)驗(yàn)，掌握算法設(shè)計(jì)與分析的一般過(guò)程，以及每個(gè)步驟的基本方法。并應(yīng)用貪心法求解單源最短路徑問(wèn)題。環(huán)境要求對(duì)于環(huán)境沒(méi)有特別要求。對(duì)于算法實(shí)現(xiàn)，可以自由選擇C,C+,Java,甚至于其他程序設(shè)計(jì)語(yǔ)言。Java實(shí)驗(yàn)步驟步驟1:理解問(wèn)題，給出問(wèn)題的描述。步驟2：算法設(shè)計(jì)，包括策略與數(shù)據(jù)結(jié)構(gòu)的選擇步驟3：描述算法。希望采用源代碼以外的形式，如偽代碼、流程圖等；步驟4：算法的正確性證明

2、。需要這個(gè)環(huán)節(jié)，在理解的基礎(chǔ)上對(duì)算法的正確性給予證明；步驟5：算法復(fù)雜性分析，包括時(shí)間復(fù)雜性和空間復(fù)雜性；步驟6：算法實(shí)現(xiàn)與測(cè)試。附上代碼或以附件的形式提交，同時(shí)貼上算法運(yùn)行結(jié)果截圖;步驟7：技術(shù)上、分析過(guò)程中等各種心得體會(huì)與備忘，需要言之有物。說(shuō)明：步驟1-6在“實(shí)驗(yàn)結(jié)果”一節(jié)中描述，步驟7在“實(shí)驗(yàn)總結(jié)”一節(jié)中描述。實(shí)驗(yàn)結(jié)果步驟1：給定一個(gè)有向帶權(quán)圖G=（V,E）,其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。另外，給定V中的一個(gè)頂點(diǎn)，稱(chēng)為源點(diǎn)。現(xiàn)在要計(jì)算從源點(diǎn)到所有其他各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度，這里的路徑長(zhǎng)度是指路徑上經(jīng)過(guò)的所有邊上的權(quán)值之和。這個(gè)問(wèn)題通常稱(chēng)為單源最短路徑問(wèn)題。步驟2：Dykstra算法思想

3、，即先求出長(zhǎng)度最短的一條路徑，再參照它求出長(zhǎng)度此短的一條路徑，以此類(lèi)推，直到從源點(diǎn)到其他各個(gè)頂點(diǎn)的最短路徑全部求出為止a：設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)。帶權(quán)鄰接矩陣C記錄結(jié)點(diǎn)之間的權(quán)值，數(shù)組dist來(lái)記錄從源點(diǎn)到其它頂點(diǎn)的最短路徑長(zhǎng)度，數(shù)組p來(lái)記錄最短路徑；b：初始化。令集合S=u,對(duì)于集合V-S中的所有頂點(diǎn)x,設(shè)置distx=Cux；如果頂點(diǎn)1與源點(diǎn)相鄰，設(shè)置pi=u,否則pi=-l：c：貪心選擇結(jié)點(diǎn)。在集合V-S中依照貪心策略來(lái)尋找使得distx具有最小值的頂點(diǎn)t,t就是集合V-S中距離源點(diǎn)u最近的頂點(diǎn)d：更新集合S和V-S。將頂點(diǎn)t加入集合S中，同時(shí)更新集合V-S：e：判斷算法是否結(jié)束。如果集合V

4、-S為空，算法結(jié)束。否則，轉(zhuǎn)步驟6；f：對(duì)相關(guān)結(jié)點(diǎn)做松地處理。對(duì)集合V-S中的所有與頂點(diǎn)t相鄰的頂點(diǎn)x,如distxdistt+Ctx,則distx=distt+Ctx并設(shè)置px=t。步驟3：unportjava.util.Scaimer;publicclassTheshoitapproachprivatestaticiiitn;G圖中的頂點(diǎn)個(gè)數(shù)privatestaticintdistent=null;/最短路徑長(zhǎng)度privatestaticiiitprevious=null;/前驅(qū)頂點(diǎn)集合publicstaticvoiddijkstra(mtv,inta.iiitdistmtfprev)單源

5、最短路徑問(wèn)題的Dijksua算法intn=dist.length-1;問(wèn)題的規(guī)模，0號(hào)元素未使用if(vn)leturn;/源不在圖中，則返回booleaiis=newbooleaiin+l;/判斷點(diǎn)是否在集合S中初始化fbi(mti=l;i=n;i+)disti=avi;源到點(diǎn)i的最短特殊路徑長(zhǎng)度si=false;點(diǎn)1現(xiàn)在不在集合S中if(disti=-1)previ=0;elseprevi=v;若最短路徑長(zhǎng)度恒為-1表示無(wú)通路，則讓點(diǎn)1的前驅(qū)點(diǎn)為0有通路則讓點(diǎn)1的前驅(qū)指向源distv=0;sv=tme;源放入集合s中fbi(mti=l;in;i+)iiittemp=Integer.MAX_

6、VALUE;iiitii=v;在剩下的點(diǎn)中除了沒(méi)有通路的點(diǎn)中找到最容易到達(dá)的，并把最容易到達(dá)的放入u中fdr(mtj=lj=nJ+)if(!sj)&(distjtemp)&(distj!=-l)U=J；temp=distu;su=true;/u放入s集合中fbr(intj=lj=nJ+)if(!sj)&(auj)!=-1)源到點(diǎn)J通過(guò)點(diǎn)u的最短特殊路徑長(zhǎng)度newdistiiitnewdist=distu+auj;if(newdistdistj|distj=-1)/通過(guò)點(diǎn)u的最短長(zhǎng)度比源直接到點(diǎn)j的最短長(zhǎng)度小或當(dāng)此路不同時(shí)執(zhí)行循環(huán)中的語(yǔ)句distj=newdist;/更新源到點(diǎn)j的最短長(zhǎng)度，di

7、stj減少了prevj=u;點(diǎn)j的前驅(qū)指向點(diǎn)u/System.out.prindn(從1出發(fā)到2、3、45的最短路徑依次為:”);fbr(intk=2;kn;k+)System.out.print(distk+n)；System.out.prmthi(distn);嚴(yán)*paramargs*/publicstaticvoidmain(Stnngargs)/TODOAuto-generatedmethodstubiiitv=1;Scannersc=newScamier(System.in);Stringline=sc.nextLine();n=Integer.parseliit(line);dis

8、tent=newintn+l;previous=newiiitn+l;iiita=newmtn+ln+1;fbr(mti=1;i=n;i+)line=sc.nextLine();Stringstr=lme.split(n”)；fbr(intj=lJ=stilengthj+)aiIj=liiteger.paiselnt(stij-1);dijkstra(v,ajistent.pievious);iiitx=previous5;iiity=previousx;iiitz=previousy;/System.out.println(”從1到5最短路徑經(jīng)過(guò)的點(diǎn)為:”);System.out.pimth

9、i(z+“+y+”+x+”“+”5”)；步驟5算法的時(shí)間復(fù)雜度為O(應(yīng))，算法的空間復(fù)雜性為O(n).步驟6Dijksua算法的正確性證明。貪心選擇性質(zhì)Dijksua算法是應(yīng)用貪心法設(shè)計(jì)策略的又一個(gè)典型例子。它所做的貪心選擇是從集合V-S中選擇具有最短路徑的頂點(diǎn)t,從而確定從源點(diǎn)u到t的最短路徑長(zhǎng)度distt,這種貪心選擇為什么能得到最優(yōu)解呢？換句話說(shuō)，為什么從源點(diǎn)到t沒(méi)有更短的其他路徑呢？事實(shí)上，假設(shè)存在一條從源點(diǎn)U到t且長(zhǎng)度比distt更短的路，設(shè)這條路徑初次走出S之外到達(dá)的頂點(diǎn)為x屬于V-S,然后徘徊于S內(nèi)外若干次，最后離開(kāi)S到達(dá)t.在這條路徑上，分別記d(u,x),d(x,t)和d(u,t)為源點(diǎn)u到頂點(diǎn)x,頂點(diǎn)x到頂點(diǎn)t和源點(diǎn)u到頂點(diǎn)t的路徑長(zhǎng)度，那么，依據(jù)假設(shè)容易得出；distx=d(u,x)d(u,x)+d(x,t)=d(u,t)=0,從而推得distxdistt.此與前提矛盾，從而證明了distt是從源點(diǎn)到頂點(diǎn)t的最短路徑長(zhǎng)度。實(shí)驗(yàn)總結(jié)這次實(shí)驗(yàn)是貪心法求單源最短路徑問(wèn)題，