文档介绍:实验一:路径选择实验
D 算法:
%D 算法 —求 V1 点到其他各点的最短路径
functionyy_d
disp('D 算法:输入图 G 的全值矩阵 W');
d=input('w=');
n=length(d);
for i=1:n
d(i,i)=inf;
end
temp=[1];
path=zeros(n);
path(:,1)=ones(n,1);
w=d(1,:);
w(1)=0;
wgt=w;
x=1;
y=1;
for i=1:n
a(i)=i;
end
disp(' 置定端集 Gp:');
for k=1:n-1
min=inf;
p=length(temp);
q=length(wgt);
for i=1:n
in1=find(temp==i);
for j=1:n
in2=find(temp==j);
ifisempty(in1)&~isempty(in2)
if wgt(i)>wgt(j)+d(j,i) wgt(i)=wgt(j)+d(j,i);
end
if min>wgt(i);
x=i;
min=wgt(i);
end
end
end
end
w(x)=wgt(x);
temp(p+1)=a(x);
for i=1:n
if w(x)==w(i)+d(i,x)
y=i;
end
end
l=1;
while path(y,l)~=0
l=l+1;
end
for i=1:l-1
path(x,i)=path(y,i);
end
path(x,l)=a(x);
disp(' 运算次数 k=');disp(k);
disp(' 此次运算得到的 Gp: ');
disp(temp);
end
disp('V1 到其他各点的最短路径及径长: ')
for i=1:n
disp(' 目的节点 i=');disp(i);
disp(' 最短路径 :')
disp(path(i,:));
disp(' 径长: ')
disp(w(i));
end
figure(1);
%hold off;
clf;
axis([1,10,0,5]);
for k=1:10
b(1,k)=k;
end
b(2,:)=rand(1,10)*5;
text(,b(2,1)+,'v1');
text(2,b(2,2)+,'v2');
text(3,b(2,3)+,'v3');
text(4,b(2,4)+,'v4');
text(5,b(2,5)+,'v5');
text(6,b(2,6)+,'v6');
text(7,b(2,7)+,'v7');
%text(8,b(2,8)+,'v8');
%text(9,b(2,9)+,'v9');
%text(10,b(2,10)+,'v10');
hold on;
for i=2:n
idage=path(i,:);
c=1;
while c<n&idage(c)~=0&idage(c+1)~=0
f=idage(c);
g=idage(c+1);
s=[b(1,f