實驗三 動態(tài)規(guī)劃法求多段圖問題

1、本科實驗報告課程名稱：算法設(shè)計與分析實驗項目：動態(tài)規(guī)劃法求多段圖問題實驗地點：專業(yè)班級：學號：學生姓名：指導(dǎo)教師：實驗三動態(tài)規(guī)劃法求多段圖問題一、實驗?zāi)康恼莆談討B(tài)規(guī)劃算法的基本思想掌握多段圖的動態(tài)規(guī)劃算法選擇鄰接表或鄰接矩陣方式來存儲圖4、分析算法求解的復(fù)雜度。二、實驗內(nèi)容設(shè)G=（V,E是一個帶權(quán)有向圖,其頂點的集合V被劃分成k2個不相交的子集Vi,lviv=k,其中V1和Vk分別只有一個頂點s（源）和一個頂點t（匯）。圖中所有邊的始點和終點都在相鄰的兩個子集Vi和Vi+1中。求一條s到t的最短路線。參考講義p136圖5-24中的多段圖,試選擇使用向前遞推算法或向后遞推算法求解多段圖問題。三、

2、實驗環(huán)境程序設(shè)計語言：C+編程工具：microsoftvisualstudio2010四、算法描述和程序代碼#include#include#include#include#defineMAX100#definen12#definek5intcnn;voidinit(intcost)/初始化圖inti,j;for(i=0;i13;i+)for(j=0;j13;j+)cij=MAX;c12=9;c13=7;c14=3;c15=2;c26=4;c27=2;c28=1;c36=2;c37=7;c48=11;c57=11;c58=8;c69=6;c610=5;c79=4;c710=3;c810=5;c

3、811=6;c912=4;c1012=2;c1112=5;voidfgraph(intcost,intpath,intd)/使用向前遞推算法求多段圖的最短路徑intr,j,temp,min;for(j=0;j=1;j-)temp=0;min=cjtemp+costtemp;/初始化最小值for(r=0;r=n;r+)if(cjr!=MAX)if(cjr+costr)min)/找到最小的rmin=cjr+costr;temp=r;costj=cjtemp+costtemp;dj=temp;path1=1;pathk=n;for(j=2;jk;j+)pathj=dpathj-1;voidbgrap

4、h(intbcost,intpath1,intd)/使用向后遞推算法求多段圖的最短路徑intr,j,temp,min;for(j=0;j=n;j+)bcostj=0;for(j=2;j=n;j+)temp=12;min=ctempj+bcosttemp;/初始化最小值for(r=0;r=n;r+)if(crj!=MAX)if(crj+bcostr)=2;i-)path1i=dpath1i+1;voidmain()intcur=-1;intcost13,d12,bcost13;intpathk;intpath1k;coutttt動態(tài)規(guī)劃解多段圖問題endl;coutnn;init(cost);f

5、graph(cost,path,d);coutvv輸出使用向前遞推算法后的最短路徑:nn;for(inti=1;iv=5;i+)coutvvpathivv;coutvvn;coutvvendlvv最短路徑為長度:vvcost1vvendl;coutvvn;coutvvn輸出使用向后遞推算法后的最短路徑:nn;bgraph(bcost,path1,d);for(i=1;iv=5;i+)coutvvpath1ivv;coutvvn;coutvvendlvv最短路徑為長度:vvbcost12vvendl;coutvvn;五、實驗結(jié)果截E:法實驗D旳期拿卷圏電-動態(tài)規(guī)劃解多段圖間題輸出使用向前謹推算法石的最短路