MATLAB中的floyd算法优化问题
本帖最后由 于 2014-7-24 11:21 编辑最近在做2011年mcm国赛B题（交巡警服务平台的配置）
用到了floyd算法求两节点之间的最短路径。
在网上找了MATLAB里的floyd函数,在第一问计算A区节点的时候效果很好，大概2分钟就出来了结果，然后同样的代码想算第二问的全市平台配置时就运算不出结果了（没报错但好几个小时都不出结果）。在此向各位前辈高手请教下是哪里出问题了，怀疑是第二问数据量太大而整个程序中的for循环太多了（但也不应该这么久啊，第二问的数据量也不至于比第一问多太多……）
废话不说上代码了：
第一问：
构建邻接矩阵clc;clear;edge=xlsread('A区内部道路联通关系');n=92; weight=inf*ones(n, n); for i=1:size(edge,1)weight(edge(i,1),edge(i,2))=edge(i,3);weight(edge(i,2),edge(i,1))=edge(i,3); weight(i,i)=0
end
附录2：定义floyd函数(n根据A区情况定义)%Floyd算法%解决最短路径问题，是用来调用的函数头文件%输入参数a是求图的带权邻接矩阵，D(i,j)表示i到j的最短距离, %输入参数a是所求图的带权邻接矩阵，i,j起点终点,min1表示i与j最短距离，path1为最短路径function=floyd(a,start,terminal)D=a;n=92;path=zeros(92,92);fori=1:n;forj=1:n; ifD(i,j)~=inf; %不相连路口距离定义为inf
path(i,j)=j; endendendfork=1:n;fori=1:n;forj=1:n; ifD(i,k)+D(k,j)<D(i,j); D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); endendendendifnargin==3 min1=D(start,terminal); m(1)=start; i=1; whilepath(m(i),terminal)~=terminal; k=i+1; m(k)=path(m(i),terminal); i=i+1; endend调用floyd函数对A区道路进行计算b=weightc=zeros(1840,3); %20个平台*92个路口为1840fori=1:20 forj=1:92 c(92*(i-1)+j,:)= endend
上述程序计算A区路口之间的关系，运行很成功
然后算第二问时我把邻接矩阵、floyd中的矩阵放大，确再也运行不出了…………PS：那些笑脸是冒号和右圆括号……论坛识别为表情了
floyd函数修改
function =floyd(a,Start,terminal)D=a;n=size(D,1);path=zeros(n,n);
主程序①（分不同城区）
clc;
clear;
edge=xlsread('all路口联通关系');
e=582;
weight=inf*ones(e,e);
for s=1:size(edge,1);
weight(edge(s,1),edge(s,2))=edge(s,3);
weight(edge(s,2),edge(s,1))=edge(s,3);
end
for t=1:582
weight1(t,t)=0;
end
%%
c=zeros(8244,3);
b=weight;
%%
%a area内部情况
for i=1:20;
for j=1:92;
c(92*(i-1)+j,:)=;
end
end
%%
%b area内部情况
for i=93:100;
for j=93:165;
c(1840+73*(i-93)+j-92,:)=;
end
end
%%
%c area内部情况
for i=166:182;
for j=166:319;
c(2424+154*(i-166)+j-165,:)=;
end
end
%%
%d area内部情况
for i=320:328;
for j=320:371;
c(5042+52*(i-320)+j-319,:)=;
end
end
%%
%e area内部情况
for i=372:386;
for j=372:474;
c(5510+103*(i-372)+j-371,:)=;
end %%
%f area内部情况
for i=475:485;
for j=475:582;
c(7055+108*(i-475)+j-474,:)=;
end
end
主程序②（不分城区582个路口全部一起算）
clc;
clear;
edge=xlsread('all路口联通关系');
e=582;
weight=inf*ones(e,e);
for s=1:size(edge,1);
weight(edge(s,1),edge(s,2))=edge(s,3);
weight(edge(s,2),edge(s,1))=edge(s,3);
end
for t=1:582
weight1(t,t)=0;
end
c=zeros(338724,3); %582的平方为3338724
b=weight1;
for i=1:size(b,1);
for j=1:size(b,2);
c(582*(i-1)+j,:)=floyd(b,i,j);
end
end
无论是主程序①还是②，运行后都长时间没反应，也不报错……到底是不是for循环太多呢？如果是要怎么提高速度……
啦
啦
啦
啦楼主改发成代码形式，方便大家看代码，在表情边上有个<>。比如……
且生 发表于 2014-7-24 21:09 static/image/common/back.gif
楼主改发成代码形式，方便大家看代码，在表情边上有个。比如……
也就一处，没关系吧
页:
[1]