圖論MATLAB算法

1、第一章：Dijkstra算法開始輸入，確定鄰接矩陣確定鄰接矩陣的節(jié)點(diǎn)數(shù)算每一個(gè)節(jié)點(diǎn)到中每一個(gè)節(jié)點(diǎn)的最小值輸出第ni個(gè)節(jié)點(diǎn)到第一個(gè)節(jié)點(diǎn)的最小距離,i=1dot結(jié)束算這個(gè)最小值的最小值，并確定其節(jié)點(diǎn)位置將第一個(gè)節(jié)點(diǎn)放入集合中將已經(jīng)確定的第節(jié)點(diǎn)到所有節(jié)點(diǎn)的權(quán)值賦為將所有節(jié)點(diǎn)到第節(jié)點(diǎn)的權(quán)值加上并代替之將第節(jié)點(diǎn)放入集合中YESNOYESNO求下面賦權(quán)圖（左圖）中頂點(diǎn)u0到其余頂點(diǎn)的最短路。其鄰接矩陣W為：function dijkstra%注：此程序僅作參考，歡迎批評(píng)指正。clcclear%Dijkstra算法: %給鄰接矩陣賦值%a=0,1,2,inf,7,inf,4,8; 1,0,2,3,inf,i

2、nf,inf,7; 0,0,0,1,5,inf,inf,inf; 0,0,0,0,3,6,inf,inf; 0,0,0,0,0,4,3,inf; 0,0,0,0,0,0,6,4; 0,0,0,0,0,0,0,2;for i=2:8 for j=1:i-1 a(i,j)=a(j,i); endenddot=size(a,1);%節(jié)點(diǎn)數(shù)fprintf('t鄰接矩陣的標(biāo)準(zhǔn)形式：');afuquantu=a;%在賦權(quán)圖中用到fprintf('t其中，inf代表無(wú)窮大,a(i,j)代表第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)的權(quán)。(1i%d;1j%d)',dot,dot);%U(1)=1;

3、%U代表已確定節(jié)點(diǎn)的集合B(1:dot,1:dot)=inf;for i=1:dot l,n(i)=min(min(a(:,U),2); L(n(i)=l; a(:,n(i)=a(:,n(i)+l; B(:,U)=a(:,U); t,m(i)=min(min(B); a(n(i),:)=inf; % a if i>2 U(i-1)=n(i); end end% n,Lnear=m;n;Lfprintf('t其中，near(3,j)表示第near(2,j)個(gè)節(jié)點(diǎn)到第1個(gè)節(jié)點(diǎn)的最短路，n該最短路徑通過邊v(near(2,j),near(1,j)。(1j%d)n',dot);%

4、為了直觀表示，做出賦權(quán)圖，為了方便起見節(jié)點(diǎn)位置由隨機(jī)數(shù)產(chǎn)生（各個(gè)節(jié)點(diǎn)的橫縱坐標(biāo)不會(huì)相等）a=fuquantu;Y=3*randperm(dot);%將1dot打亂順序，保證各個(gè)節(jié)點(diǎn)的橫縱坐標(biāo)不會(huì)相等X=3*randperm(dot); hold on axis equalfor i=1:dot-1 for j=i+1:dot if a(i,j)=inf% plot(X(i),Y(i),X(j),Y(j) plot(X(i),X(j),Y(i),Y(j),'linewidth',3); hold on text(2*X(i)+X(j)/3,(2*Y(i)+Y(j)/3,num2s

5、tr(a(i,j),'Rotation',180/pi*atan(Y(j)-Y(i)/(X(j)-X(i),'FontSize',18,'VerticalAlignment','cap')%將權(quán)值標(biāo)在1/3等分點(diǎn)位置，方向與傾斜角對(duì)應(yīng)，便于區(qū)分 end endendhold onfor i=2:dot plot(X(near(1,i),X(near(2,i),Y(near(1,i),Y(near(2,i),'linewidth',3,'color','r'); % text(2*X(

6、near(1,i)+X(near(2,i)/3,(2*Y(near(1,i)+Y(near(2,i)/3,num2str(a(near(1,i),near(2,i),'Rotation',180/pi*atan(Y(near(2,i)-Y(near(1,i)/(X(near(2,i)-X(near(1,i),'FontSize',18)endplot(X,Y,'o','markersize',20,'MarkerEdgeColor','g','MarkerFaceColor',

7、9;g');for i=1:dot text(X(i),Y(i),'n',num2str(i-1),'HorizontalAlignment','center');%為了美觀，保證(x,y)在文本text中心end注:標(biāo) 部分是通過網(wǎng)上查找的資料再借助doc命令寫出來的 運(yùn)行結(jié)果：鄰接矩陣的標(biāo)準(zhǔn)形式：a = 0 1 2 Inf 7 Inf 4 8 1 0 2 3 Inf Inf Inf 7 2 2 0 1 5 Inf Inf Inf Inf 3 1 0 3 6 Inf Inf 7 Inf 5 3 0 4 3 Inf Inf Inf Inf

8、 6 4 0 6 4 4 Inf Inf Inf 3 6 0 2 8 7 Inf Inf Inf 4 2 0其中，inf代表無(wú)窮大,a(i,j)代表第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)的權(quán)。(1i8;1j8)near = 1 1 1 3 1 4 7 4 1 2 3 4 7 5 8 6 0 1 2 3 6 9 4 6其中，near(3,j)表示第near(2,j)個(gè)節(jié)點(diǎn)到第1個(gè)節(jié)點(diǎn)的最短路，該最短路徑通過邊v(near(2,j),near(1,j)。(1j8)其他例子：運(yùn)行結(jié)果：鄰接矩陣的標(biāo)準(zhǔn)形式：a = 0 2 5 3 Inf Inf Inf Inf 2 0 4 Inf 6 Inf Inf Inf 5 4

9、0 4 Inf 5 Inf Inf 3 Inf 4 0 Inf Inf 4 Inf Inf 6 Inf Inf 0 3 Inf 4 Inf Inf 5 Inf 3 0 5 4 Inf Inf Inf 4 Inf 5 0 6 Inf Inf Inf Inf 4 4 6 0其中，inf代表無(wú)窮大,a(i,j)代表第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)的權(quán)。(1i8;1j8)near = 1 1 1 1 4 2 3 5 1 2 4 3 7 5 6 8 0 2 3 5 7 8 10 12其中，near(3,j)表示第near(2,j)個(gè)節(jié)點(diǎn)到第1個(gè)節(jié)點(diǎn)的最短路，該最短路徑通過邊v(near(2,j),near(1,j

10、)。(1j8)與參考答案比較，一模一樣：第二章：Floyd算法function floydclcclear%用floyd算法實(shí)現(xiàn)求任意兩點(diǎn)之間的最短路程。%參數(shù)a為連通圖的權(quán)矩陣 % a=0 2 8 1 inf inf inf inf % 2 0 6 inf 1 inf inf inf % 8 6 0 7 5 1 2 inf % 1 inf 7 0 inf inf 9 inf % inf 1 5 inf 0 3 inf 8 % inf inf 1 inf 3 0 4 6 % inf inf 2 9 inf 4 0 3 % inf inf inf inf 8 6 3 0;% a =0 1 Inf

11、 Inf Inf 2% 1 0 4 Inf Inf 4% Inf 4 0 2 Inf 1% Inf Inf 2 0 3 3% Inf Inf Inf 3 0 5% 2 4 1 3 5 0;a =0 2 5 3 Inf Inf Inf Inf 2 0 4 Inf 6 Inf Inf Inf 5 4 0 4 Inf 5 Inf Inf 3 Inf 4 0 Inf Inf 4 Inf Inf 6 Inf Inf 0 3 Inf 4 Inf Inf 5 Inf 3 0 5 4 Inf Inf Inf 4 Inf 5 0 6 Inf Inf Inf Inf 4 4 6 0 dot=size(a,1);%

12、確定節(jié)點(diǎn)數(shù)for i=1:dot for j=1:dot R(i,j)=j; end end for k=1:dot for i=1:dot for j=1:dot if a(i,k)+a(k,j)<a(i,j) a(i,j)=a(i,k)+a(k,j);%更新 a(i,j)，使通過點(diǎn)k的權(quán)更小 R(i,j)=R(i,k);%更新R(i,j)，需要通過點(diǎn)k end end endendafprintf('ta(i,j)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)的最短權(quán)距離(1i%d,1j%d)',dot,dot);Rfprintf('tR(i,j)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)的最短

13、路徑必須通過邊v(i,R(i,j)(1i%d,1j%d)n',dot,dot);%為了便于顯示，輸出最短路徑for i=1:dot for j=1:dot distance=i; for k=1:dot if distance(k)=j fprintf('第%d節(jié)點(diǎn)與第%d節(jié)點(diǎn)的最短路徑為：',i,j); fprintf('%d',distance); fprintf('n'); break; else distance(k+1)=R(distance(k),j); end end endend運(yùn)行結(jié)果：a = 0 2 5 3 Inf I

14、nf Inf Inf 2 0 4 Inf 6 Inf Inf Inf 5 4 0 4 Inf 5 Inf Inf 3 Inf 4 0 Inf Inf 4 Inf Inf 6 Inf Inf 0 3 Inf 4 Inf Inf 5 Inf 3 0 5 4 Inf Inf Inf 4 Inf 5 0 6 Inf Inf Inf Inf 4 4 6 0a = 0 2 5 3 8 10 7 12 2 0 4 5 6 9 9 10 5 4 0 4 8 5 8 9 3 5 4 0 11 9 4 10 8 6 8 11 0 3 8 4 10 9 5 9 3 0 5 4 7 9 8 4 8 5 0 6 12

15、10 9 10 4 4 6 0a(i,j)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)的最短權(quán)距離(1i8,1j8)R = 1 2 3 4 2 3 4 2 1 2 3 1 5 3 1 5 1 2 3 4 6 6 4 6 1 1 3 4 1 3 7 7 2 2 6 2 5 6 6 8 3 3 3 3 5 6 7 8 4 4 4 4 6 6 7 8 5 5 6 7 5 6 7 8R(i,j)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)的最短路徑必須通過邊v(i,R(i,j)(1i8,1j8)第1節(jié)點(diǎn)與第1節(jié)點(diǎn)的最短路徑為：1第1節(jié)點(diǎn)與第2節(jié)點(diǎn)的最短路徑為：12第1節(jié)點(diǎn)與第3節(jié)點(diǎn)的最短路徑為：13第1節(jié)點(diǎn)與第4節(jié)點(diǎn)的最短路徑為：14第

16、1節(jié)點(diǎn)與第5節(jié)點(diǎn)的最短路徑為：125第1節(jié)點(diǎn)與第6節(jié)點(diǎn)的最短路徑為：136第1節(jié)點(diǎn)與第7節(jié)點(diǎn)的最短路徑為：147第1節(jié)點(diǎn)與第8節(jié)點(diǎn)的最短路徑為：1258第2節(jié)點(diǎn)與第1節(jié)點(diǎn)的最短路徑為：21第2節(jié)點(diǎn)與第2節(jié)點(diǎn)的最短路徑為：2第2節(jié)點(diǎn)與第3節(jié)點(diǎn)的最短路徑為：23第2節(jié)點(diǎn)與第4節(jié)點(diǎn)的最短路徑為：214第2節(jié)點(diǎn)與第5節(jié)點(diǎn)的最短路徑為：25第2節(jié)點(diǎn)與第6節(jié)點(diǎn)的最短路徑為：236第2節(jié)點(diǎn)與第7節(jié)點(diǎn)的最短路徑為：2147第2節(jié)點(diǎn)與第8節(jié)點(diǎn)的最短路徑為：258第3節(jié)點(diǎn)與第1節(jié)點(diǎn)的最短路徑為：31第3節(jié)點(diǎn)與第2節(jié)點(diǎn)的最短路徑為：32第3節(jié)點(diǎn)與第3節(jié)點(diǎn)的最短路徑為：3第3節(jié)點(diǎn)與第4節(jié)點(diǎn)的最短路徑為：34第3節(jié)點(diǎn)與

17、第5節(jié)點(diǎn)的最短路徑為：365第3節(jié)點(diǎn)與第6節(jié)點(diǎn)的最短路徑為：36第3節(jié)點(diǎn)與第7節(jié)點(diǎn)的最短路徑為：347第3節(jié)點(diǎn)與第8節(jié)點(diǎn)的最短路徑為：368第4節(jié)點(diǎn)與第1節(jié)點(diǎn)的最短路徑為：41第4節(jié)點(diǎn)與第2節(jié)點(diǎn)的最短路徑為：412第4節(jié)點(diǎn)與第3節(jié)點(diǎn)的最短路徑為：43第4節(jié)點(diǎn)與第4節(jié)點(diǎn)的最短路徑為：4第4節(jié)點(diǎn)與第5節(jié)點(diǎn)的最短路徑為：4125第4節(jié)點(diǎn)與第6節(jié)點(diǎn)的最短路徑為：436第4節(jié)點(diǎn)與第7節(jié)點(diǎn)的最短路徑為：47第4節(jié)點(diǎn)與第8節(jié)點(diǎn)的最短路徑為：478第5節(jié)點(diǎn)與第1節(jié)點(diǎn)的最短路徑為：521第5節(jié)點(diǎn)與第2節(jié)點(diǎn)的最短路徑為：52第5節(jié)點(diǎn)與第3節(jié)點(diǎn)的最短路徑為：563第5節(jié)點(diǎn)與第4節(jié)點(diǎn)的最短路徑為：5214第5節(jié)點(diǎn)與第

18、5節(jié)點(diǎn)的最短路徑為：5第5節(jié)點(diǎn)與第6節(jié)點(diǎn)的最短路徑為：56第5節(jié)點(diǎn)與第7節(jié)點(diǎn)的最短路徑為：567第5節(jié)點(diǎn)與第8節(jié)點(diǎn)的最短路徑為：58第6節(jié)點(diǎn)與第1節(jié)點(diǎn)的最短路徑為：631第6節(jié)點(diǎn)與第2節(jié)點(diǎn)的最短路徑為：632第6節(jié)點(diǎn)與第3節(jié)點(diǎn)的最短路徑為：63第6節(jié)點(diǎn)與第4節(jié)點(diǎn)的最短路徑為：634第6節(jié)點(diǎn)與第5節(jié)點(diǎn)的最短路徑為：65第6節(jié)點(diǎn)與第6節(jié)點(diǎn)的最短路徑為：6第6節(jié)點(diǎn)與第7節(jié)點(diǎn)的最短路徑為：67第6節(jié)點(diǎn)與第8節(jié)點(diǎn)的最短路徑為：68第7節(jié)點(diǎn)與第1節(jié)點(diǎn)的最短路徑為：741第7節(jié)點(diǎn)與第2節(jié)點(diǎn)的最短路徑為：7412第7節(jié)點(diǎn)與第3節(jié)點(diǎn)的最短路徑為：743第7節(jié)點(diǎn)與第4節(jié)點(diǎn)的最短路徑為：74第7節(jié)點(diǎn)與第5節(jié)點(diǎn)的最短路徑為：765第7節(jié)點(diǎn)與第6節(jié)點(diǎn)的最短路徑為：76第7節(jié)點(diǎn)與第7節(jié)點(diǎn)的最短路徑為：7第7節(jié)點(diǎn)與第8節(jié)點(diǎn)的最短路徑為：78第8節(jié)點(diǎn)與第1節(jié)點(diǎn)的最短路徑為：8521第8節(jié)點(diǎn)與第2節(jié)點(diǎn)的最短路徑為：852第8節(jié)點(diǎn)與第3節(jié)點(diǎn)的最短路徑為：86