計算機仿真期末作業姓名：吳隱奎班級：04601學號：041751日期：2007-6-15題目：Floyd算法實現和分析內容：用MATLAB仿真工具實現Floyd算法，求任意兩端間的最短路徑。要求：盡可能用M函數分別實現算法的關鍵部分，用M腳本來進行算法結果驗證；分別用以下兩個圖（用初始距離矩陣表示）進行算法驗證：-01001001.29.21000.5_圖一：W⑼=|0.521.51001001000]_-00.521.5100100100-圖二：W（o）=L1001003.1410015.60算法：給定圖g及其邊色力的權卬（l<z<n,l<j<n）F0：初始化距離矩陣W（。）和路由矩陣R。）。其中：w若ewE（有邊）卬（0）=<00若e紀E（無邊）ij0若i=j（對角線元素）。）=[j若'0,其它Fl：已求得和Rbi）,依據下面的迭代求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,重復F1；若k=n,終止。仿真：用四個m文件來實現仿真，其中main為主函數，首先測試出矩陣的長度，然后賦給n,作為循環的次數；然后調用fund實現路由矩陣的初始化，把第k-1次的值付給a后，調用func2函數來迭代求出k次的w值，調用func3函數，根據a(實際上為k-1次w值)值和k次w值來求出k次r值。迭代循環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實現路由矩陣的初始化主要程序fori=l:1:nforj=l:1:nifx(i,j)==100rO(i,j)=0;elserO(i,j)=j;end,end;end;Iruuc2該函數實現的功能是根據k-1次w的值迭代求k次w的值主要程序fori=l:nforj=l:nw(i,j)=min(s(i,j),s(i,k)+s(k,j));endendFunc3來根據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結果：圖一的結果：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圖二的結果：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端點對V1和V7之間最短距離是5.1,最短路由是V1—>V3—>V7端點對V3和V5之間最短距離是3.7,最短路由是V3—>V1—>V2—>V5端點對V1和V6之間最短距離是8.4,最短路由是V1—>V2—>V5—>V6總結：通過一個學期計算機仿真課的學習，我現在已經能很熟練的使用的仿真工具matlab來進行