最短路计算法度模范.doc
文本预览下载声明
最短路计算程序
%css
clear all
clc
b=inf;
G1=[ 0, 19, b, 17, 35; % ±?3¤???ó￡¨?±í¨?·3¤?à?ó￡?
19, 0, 40, 31, b;
b, 40, 0, 20, b;
17, 31, 20, 0, 15;
35, b, b, 15, 0];
G=G1;
n=size(G,1);
v0=2;
v1=ones(1,n); % ?????????¨???????
v1(v0)=0;
D=G(v0,:);
while 1 %1
D2=D;
for i=1:n
if v1(i)==0
D2(i)=inf;
end
end
D2;
[Dmin,ind]=min(D2);
v0=[v0,ind]; %?¨???
v1(ind)=0;
if size(v0,2)==n
break;
end
ind=0; % ??
for j=1:n % ?¨???j???á??¨1?¨¤??
if v1(j)~=0
for i=1:n
if v1(i)==0 % i??v0??
D(j)=min(D(j),D(i)+G(i,j));
end
D(j)=min(D(j),G(v0(1),i)+G(i,j));
end
end
end
end
v0,
[[1:n],D],
显示全部