怎么根据Floyd算法 从多个顶点中选出几个，使其他
编辑： admin 2017-12-03
-
4
先用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,:) %最佳的缴费点的选择.
类似问题
类似问题1：用c++实现 利用BFS算法在图中求各顶点与搜索起点间的最短距离在无权有向图中,两个顶点之间的距离定义为：如果顶点i经过k步到达顶点j,则顶点i到顶点j的距离为k.怎么用c++,利用BFS求得一个
用队列来做就可以了
类似问题2：图中,判断那两个顶点距离最远.采用广度优先算法?c语言编写
#include
int main(void)
{
int n;
int i,j,k;
int g[100][100];
scanf("%d",&n);
for(j=0;j
类似问题3：急救,已知有向图如下,利用迪杰特拉算法（Dijkstra),求V0到各顶点的最短距离和路线,即填写如下表格.终点\x09从V0到各终点的dist值和最短距离V1\x09\x09\x09\x09\x09V2\x09\x09\x09\x09\x09V3\x09\x09\x09\x09\x09V4[数学科目]
我擦,太难了
类似问题4：我有一个73*73的距离矩阵,想用floyd算法求一下任意两点之间的最短距离,您能把程序给我发一下吗?还有怎么运用?以及路径的输出,我要做一个运筹学的题目,需要floyd算法,hi交谈也可以,[数学科目]
嗯
类似问题5：floyd算法计算出距离矩阵之后怎么做[数学科目]
你想实现什么?