図論の中で最も短いアルゴリズムとプログラムの実現

図論における最短回路問題(無方向図と有方向図を含む)は基本的でよく見られる問題である.主なアルゴリズムはDijkstrasアルゴリズムとFloydアルゴリズムである.
Dijkstraアルゴリズムは,指定された2点間の最短ルートを求めるアルゴリズムであり,アルゴリズム複雑度O(n^2)
Floydアルゴリズムは任意の2点間の最短ルートを求めるアルゴリズムであり,アルゴリズム複雑度O(n^3)
2.Floydアルゴリズム
1)既知の部分ノード間のリンク情報に基づいて、更新を容易にするために十分な大きな距離を与えない初期行列B(i,j)が確立される.
2)反復計算を行う.任意の2点(i,j)に対して、kが存在する場合、B(i,k)+B(k,j)
3)全ての点距離が更新されなくなるまで計算を停止し、最短距離行列B(i,j)を得る
アルゴリズムプログラム(Matlab)は次のとおりです.

for k=1:n
 for i=1:n
  for j=1:n
      t=B(i,k)+B(k,j);
      if tt;
     end
   end
  end
end

50個の点の間で互いに情報を接続することを知っていて、最短距離のマトリックスを求めます.
 

n=50;%Matlab   Floyd  
A=zeros(n,n);
for i=1:n
    for j=1:n
        if(i==j) 
            A(i,j)=0;
        else
            A(i,j)=100000;
        end
    end
end %       
A(1,2)=400;A(1,3)=450; A(2,4)=300;A(2,21)=230; A(2,47)=140;A(3,4)=600;
A(4,5)=210;A(4,19)=310;A(5,6)=230;A(5,7)=200; A(6,7)=320; A(6,8)=340;
A(7,8)=170;A(7,18)=160;A(8,9)=200;A(8,15)=285; A(9,10)=180; A(10,11)=150;
A(10,15)=160; A(11,12)=140; A(11,14)=130; A(12,13)=200; A(13,34)=400;
A(14,15)=190;A(14,26)=190; A(15,16)=170; A(15,17)=250; A(16,17)=140;
A(16,18)=130; A(17,27)=240; A(18,19)=204; A(18,25)=180; A(19,20)=140;
A(19,24)=175; A(20,21)=180; A(20,24)=190; A(21,22)=300; A(21,23)=270;
A(21,47)=350;A(22,44)=160;A(22,45)=270;A(22,48)=180;A(23,24)=240;
A(23,29)=210;A(23,30)=290;A(23,44)=150;A(24,25)=170;A(24,28)=130;
A(26,27)=140;A(26,34)=320;A(27,28)=190;A(28,29)=260;A(29,31)=190;
A(30,31)=240;A(30,42)=130;A(30,43)=210;A(31,32)=230;A(31,36)=260;
A(31,50)=210;A(32,33)=190;A(32,35)=140;A(32,36)=240;A(33,34)=210;
A(35,37)=160;A(36,39)=180;A(36,40)=190;A(37,38)=135;A(38,39)=130;
A(39,41)=310;A(40,41)=140;A(40,50)=190;A(42,50)=200;A(43,44)=260;
A(43,45)=210;A(45,46)=240;A(46,48)=280;A(48,49)=200;
for j=1:n
    for i=1:j-1
        A(j,i)=A(i,j);%     
    end
end
B=A;
%  Floyd          
for k=1:n
    for i=1:n
        for j=1:n
            t=B(i,k)+B(k,j);
            if t<B(i,j) 
                B(i,j)=t; 
            end
        end
    end
end
%         
fid=fopen('distance.txt','w');
for i=1:n
    for j=1:n
        fprintf(fid,'%6d',B(i,j));
    end
    fprintf(fid,'
');
end
fclose(fid);

テキストリンク:https://www.icourse163.org/
交流は個人の微信の公衆番号に注目してください:dankekang