学帮网怎么根据Floyd算法 从多个顶点中选出几个,使其他点到选出点距离最短?貌似我看到的都是只能到一个点
来源：学生作业学帮网 编辑：学帮网 时间：2024/05/06 01:24:42
怎么根据Floyd算法 从多个顶点中选出几个,使其他点到选出点距离最短?
貌似我看到的都是只能到一个点
先用floyd求出距离矩阵D,即以下代码中的矩阵B.
以下matlab程序为从12个点中选出3点,可以此类推.
clear all;
A=[combntns(1:12,3)]; %列出12个居民点选3个缴费点的所有情况.
for i=1:nchoosek(12,3) %for……end,循环,计算以上列出所有情况下所有居民需要行走的总路程!
A2=A(i,:);
A3=A2(1,1); %读取选取3个居民点
A4=A2(1,2);
A5=A2(1,3);
People=[15 10 12 18 5 24 11 16 13 22 19 20]; %每个居民点的人数的矩阵.
B=[
0 15 37 55 24 60 18 33 48 40 58 67;
15 0 22 40 38 52 33 48 42 55 61 61;
37 22 0 18 16 30 43 28 20 58 39 39;
55 40 18 0 34 12 61 46 24 62 43 34;
24 38 16 34 0 36 27 12 24 49 37 43;
60 52 30 12 36 0 57 42 12 50 31 22;
18 33 43 61 27 57 0 15 45 22 40 61;
33 48 28 46 12 42 15 0 30 37 25 46;
48 42 20 24 24 12 45 30 0 38 19 19;
40 55 58 62 49 50 22 37 38 0 19 40;
58 61 39 43 37 31 40 25 19 19 0 21;
67 61 39 34 43 22 61 46 19 40 21 0 ;
]; %居民到其他居民点所有最短的距离.
B1=B(:,A3); %居民点到所选的缴费点的理论最短距离.
B2=B(:,A4);
B3=B(:,A5);
C=[B1 B2 B3];
D=sort(C,2);
Shortjourney=D(:,1); %每位居民选择缴费点后需要行走的最短路程.
Sum(i)=People*Shortjourney; %所有居民所要行走的路程总和.
end
E=[reshape(Sum,nchoosek(12,3),1)]; %将以上得到的数组转为矩阵.
minposition=find(E==min(E)); %找出最小值在矩阵的位置.
A=[combntns(1:12,3)]; %A的顺序与E的一致!
position=A(minposition,:) %最佳的缴费点的选择.