1、湖南大學湖南大學MATLAB實訓報告目：matlab計算最短路徑問題學院名稱：信息科學與工程學院專業班級：軟件工程四班學生姓名：彭天越學 號：20112601416日 期：2013年7月3號湖南大學目錄題目 2問題描述 3(1) 根據無向圖A,使用Di.jistra 算法 3(2) 根據有向圖B,使用 Warshall-Floyd 算法 4思路及代碼 4(1) 思路 4(2) 源代碼 5測試結果說明 10(1) Di.jistra算法 10(2) Floyd 算法 11小結 11題巨求下圖中頂點 折到頂點31的最短距離和最短路(2學分)VIIA無向囹3B.有向圖問題描述(1)根據無向圖A,使用

2、Di.jistra算法V11A無向囹湖南大學城用布火鄉7根據有向圖,使用 Warshall-Floyd 算法思路及代碼思路(1) Dijkstra 算法使用范圍：1) 尋求從一固定頂點到其余各點的最短路徑；2) 有向圖、無向圖和混合圖；3) 權非負.算法思路：采用標號作業法，每次迭代產生一個永久標號，從而生長一顆 以Vo為根的最短路樹，在這顆樹上每個頂點與根節點之間的路徑皆為最短路徑 . 訴法步驟：S:具有永久標號的頂點集；l(v): V 的標記；f(v):v 的父頂點，用以確定最短路徑；輸入加權圖的帶權鄰接矩陣 W=W(Vi,Vj) nxm.1) 初始化 令 l(v o)=O,S=p V V

3、#Vo ,l(v)=°°；2) 更新 l(v), f(v)尋找不在S中的頂點u,使l(u)為最小.把u加入到S中，然后對所有不在S中的 頂點 v,如 l(v)>l(u)+w(u,v),貝U 更新 l(v),f(v), 即l(v)，l(u)+w(u,v),f(v)' u；3) 重復步驟2),直到所有頂點都在S中為止.(2) Floyd 算法使用范圍：1) 求每對頂點的最短路徑；2) 有向圖、無向圖和混合圖；邕)浙槌4算法思想：直接在圖的帶權鄰接矩陣中用插入頂點的方法依次遞推地構造出n個矩陣D(1),D(2),，D(n), D(n)是圖的距離矩陣，同時引入一個后繼

4、點矩陣記錄兩點間的 最短路徑.算法步驟：d(i,j) : i 到j的距離；path(i,j): i 到j的路徑上i的后繼點；輸入帶權鄰接矩陣a(i,j).1) 賦初值對所有 i,j, d(i,j) - a(i,j) , path(i,j) - j,k=l.2) 更新 d(i,j) , path(i,j)對所有 i,j,若 d(i,k)+d(k,j)<d(i,j),貝Ud(i,j), d(i,k)+d(k,j) , path(i,j) , path(i,k) , k , k+13) 重復2)直到k=n+1(2)源代碼(1) Dijkstra.m 文件咐算最短路徑(Dijkstra 算法)%

5、min表示最短的距離%path表示最短路徑%wK示鄰接矩陣%start表示開始點%terminal表示終止點function min,path=dijkstra(w,start,terminal)n=size(w,1); % 計算鄰接矩陣的行數label(start)=0; f(start)=start;%初始化for i=1:nif i=startlabel(i)=inf;endends(1)=start; u=start;咖新最短路徑直到所有頂點都遍歷while length(s)<nfor i=1:nins=0;for j=1:length(s)if i=s(j)ins=1;end

6、endif ins=0v=i;if label(v)>(label(u)+w(u,v)label(v)=(label(u)+w(u,v);f(v)=u;endendend%v1=0;k=inf;for i=1:nins=0;for j=1:length(s)if i=s(j)ins=1;endendif ins=0v=i;if k>label(v)k=label(v);v1=v;endendends(length(s)+1)=v1;u=v1;end%求出最短距離與最短路徑min=label(terminal); path(1)=terminal; i=1;while path(i)

7、=startpath(i+1)=f(path(i);i=i+1 ;endpath(i)=start;L=length(path);path=path(L:-1:1);% 循環輸出路徑text01.m腳本文件進行測試clear;clc;fprintf('計算最短路徑(Dijkstra 算法)n');x=0,2,1,8,inf,inf,inf,inf,inf,inf,inf;2,0,inf,6,1,inf,inf,inf,inf,inf,inf;1,inf,0,7,inf,inf,9,inf,inf,inf,inf;8,6,7,0,5,1,2,inf,inf,inf,inf;inf

8、,1,inf,5,0,3,inf,2,1,inf,inf;inf,inf,inf,1,3,0,4,inf,6,inf,inf;inf,inf,9,2,inf,4,0,inf,3,1,inf;inf,inf,inf,inf,2,inf,inf,0,7,inf,inf;inf,inf,inf,inf,inf,6,3,7,0,1,2;inf,inf,inf,inf,inf,inf,1,inf,1,0,1;inf,inf,inf,inf,inf,inf,inf,inf,2,1,0%x=input('輸入鄰接矩陣:');start=input('輸入起點：)；terminal=i

9、nput('輸入終點：');fprintf('計算結果如下：');min,path_way=dijkstra(x,start,terminal)Floyd.m 函數以的算最短路徑(Floyd算法)%D,path,min1,path1=floyd(a,start,terminal) 返回矩陣 D, path; 并返回 start 與terminal之間的最短距離 min 1和最短路徑path1.%path(i,j):表示i到j的路徑上i的后繼點；%D(i,j):表示i到j的距離；以輸入帶權鄰接矩陣a(i,j).%1賦初值%對所有 i,j, D(i,j)<-a

10、(i,j) , path(i,j)<-j湖南大學%2 更新 D(i,j) , path(i,j)%對所有 i,j, 若 D(i,k)+D(k,j)<d(i,j), 則%D(i,j)<-D(i,k)+D(k,j) , path(i,j)<-path(i,k) , k<-k+1%3重復2)直到k=n+1function D,path,min1,path1=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n);% 初女臺化for i=1:nfor j=1:n if D(i,j)=inf path(i,j)=j;e

11、ndendendfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendendif nargin=3% 參數個數為3的時候執行min1=D(start,terminal);%最短距離m(1)=start;i=1;path1= ; %計算最短路徑while path(m(i),terminal)=terminalk=i+1;m(k)=path(m(i),terminal);i=i+1;endm(i+1)=terminal;path1=m;endt

12、ext02.m腳本文件，進行測試clear;clc;fprintf（'計算最短路徑（Floyd算法）n'）;x=0,2,inf,8,inf,inf,inf,inf,inf,inf,inf;inf,0,inf,6,1,inf,inf,inf,inf,inf,inf;1,inf,0,inf,inf,inf,9,inf,inf,inf,inf;inf,inf,7,0,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,5,0,inf,inf,inf,1,inf,inf;inf,inf,inf,1,3,0,4,inf,inf,inf,inf;inf,inf,

13、inf,2,inf,inf,0,inf,3,1,inf;inf,inf,inf,inf,2,inf,inf,0,inf,inf,inf;inf,inf,inf,inf,inf,6,inf,7,0,inf,inf;inf,inf,inf,inf,inf,inf,inf,inf,1,0,1;inf,inf,inf,inf,inf,inf,inf,inf,2,inf,0%x=input（'輸入鄰接矩陣:'）;start=input（'輸入起點：）；terminal=input（'輸入終點：'）;fprintf（'計算結果如下：'）;D,path

14、,min,path_way=floyd（x,start,terminal）9湖南大學測試結果說明(l)Di.jistra 算法訐算最短路徑(Di jkMg算法x -02IInfTnfInfInfInfInfInf20Inf61InfInf&InfInfInf1Inf07InfInf9InfInfInfInf060512InfInfInfInfInf1Inf503Inf21InfInfItrfInfInf1304Inf6InfInfIrrfInf92Inf40Inf31InfInfInfInfInf2InfInf01IiifMInfInfInfInfInf637012IrrfInfInf

15、IrrfInfInf1InfI1IrrfInfInfInfInfInfInfInf210輸入起點：1輸入綣點：11計算結果如下、min =6path_way =125911根據無向圖A,可以知道matlab計算出來的結果是正確的(2)Floyd 算法計莒最疽路徑任甬殉其法)Inf Inf Inf Inf Inf InfInf Inf Inflitnflit1rLfInfInfnfInfIInfInfInfnrrfnfn-fIrfn'fMnf I I I I I I I nfl'SMRfnfHnf I I I I I I LIrfIirfInfInfInfInfInfInE101InfInfInfInfInfInfInfInf2Inf0輸入起點：1輸入終點；11iriiri -16pathway -12596 T 10 H根據有