最短路徑matlab計(jì)算機(jī)仿真

計(jì)算機(jī)仿真期末作業(yè)姓名：吳隱奎班級(jí)：04601學(xué)號(hào)：041751日期：2007-6-15題目：Floyd算法實(shí)現(xiàn)和分析內(nèi)容：用MATLAB仿真工具實(shí)現(xiàn)Floyd算法，求任意兩端間的最短路徑。要求：盡可能用M函數(shù)分別實(shí)現(xiàn)算法的關(guān)鍵部分，用M腳本來(lái)進(jìn)行算法結(jié)果驗(yàn)證；分別用以下兩個(gè)圖（用初始距離矩陣表示）進(jìn)行算法驗(yàn)證：-01001001.29.21000.5_圖一：W⑼=|0.521.51001001000]_-00.521.5100100100-圖二：W（o）=L1001003.1410015.60算法：給定圖g及其邊色力的權(quán)卬（l<z<n,l<j<n）F0：初始化距離矩陣W（。）和路由矩陣R。）。其中：w若ewE（有邊）卬（0）=<00若e紀(jì)E（無(wú)邊）ij0若i=j（對(duì)角線元素）。）=[j若'0,其它Fl：已求得和Rbi）,依據(jù)下面的迭代求W伙）和R伙）w（k）=min（w-i）,卬伏-i）+卬伏川）i,ji,ji,kk,jr(j)若w伏)<w(*-1)r(Jt)=i,k什i,ji.ji.jr(Jt-1)右卬(k)=W(2-1)Iiji，ji，jF2：若k<n,重復(fù)F1；若k=n,終止。仿真：用四個(gè)m文件來(lái)實(shí)現(xiàn)仿真，其中main為主函數(shù)，首先測(cè)試出矩陣的長(zhǎng)度，然后賦給n,作為循環(huán)的次數(shù)；然后調(diào)用fund實(shí)現(xiàn)路由矩陣的初始化，把第k-1次的值付給a后，調(diào)用func2函數(shù)來(lái)迭代求出k次的w值，調(diào)用func3函數(shù)，根據(jù)a(實(shí)際上為k-1次w值)值和k次w值來(lái)求出k次r值。迭代循環(huán)n次。主要程序：n=length(w);refund(w,n);fork=l:na=w;w=func2(w,n,k);r=func3(a,w,r,n,k);end;Fund實(shí)現(xiàn)路由矩陣的初始化主要程序fori=l:1:nforj=l:1:nifx(i,j)==100rO(i,j)=0;elserO(i,j)=j;end,end;end;Iruuc2該函數(shù)實(shí)現(xiàn)的功能是根據(jù)k-1次w的值迭代求k次w的值主要程序fori=l:nforj=l:nw(i,j)=min(s(i,j),s(i,k)+s(k,j));endendFunc3來(lái)根據(jù)k-1次w值和k次w值的大小求k次R的值主要程序：fori=l:nforj=l:nifi==jr(i,j)=0;elseifw(i,j)<a(i,j)r(i,j)=r(i,k);

elser(i,j)=r(i,j);endendend結(jié)果：圖一的結(jié)果：w=02.50002.00001.20007.90005.60000.50002.500003.50003.700010.4()003.10002.00002.00003.500003.20009.90004.00001.50001.20003.70003.200006.70006.80001.70007.900010.40009.90006.7000013.50008.40005.60003.10004.00006.800013.500005.10000.50002.00001.50001.70008.40005.10000r=0774477707776777077671110511444404422322021231120可以看出：V4和V6之間最短距離是6.8,最短路由是V4—>V1—>V7—>V2—>V6V3和V4之間最短距離是3.2,最短路由是V3—>V7—>V1—>V4圖二的結(jié)果：w=00.50002.00001.50001.70008.40005.10000.500002.50002.00001.20007.90005.60002.00002.500003.50003.700010.40003.10001.50002.00003.500003.20009.90004.00001.70001.20003.70003.200006.70006.80008.40007.900010.40009.90006.7000013.50005.10005.60003.10004.00006.800013.50000r二0234223101155111011171110117222206255555053334330端點(diǎn)對(duì)V1和V7之間最短距離是5.1,最短路由是V1—>V3—>V7端點(diǎn)對(duì)V3和V5之間最短距離是3.7,最短路由是V3—>V1—>V2—>V5端點(diǎn)對(duì)V1和V6之間最短距離是8.4,最短路由是V1—>V2—>V5—>V6總結(jié)：通過(guò)一個(gè)學(xué)期計(jì)算機(jī)仿真課的學(xué)習(xí)，我現(xiàn)在已經(jīng)能很熟練的使用的仿真工具matlab來(lái)進(jìn)行