下面这段程序是利用Dijkstra算法求最短路径,可能学过计算数学的人会有一定印象,也希望那些参加数学建模竞赛的人能用得上。
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all
clc
M=10000;
a(1,:)=[0,50,M,40,25,10]; %%%生成邻接矩阵
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';
pb(1:length(a))=0;
pb(1)=1;
index1=1;
index2=ones(1,length(a));
d(1:length(a))=M;
d(1)=0;
temp=1;
while sum(pb)<length(a)
tb=find(pb==0);
d(tb)=min(d(tb),d(temp)+a(temp,tb));
tmpb=find(d(tb)==min(d(tb)));
temp=tb(tmpb(1));
pb(temp)=1;
index1=[index1,temp];
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index;
end
d, index1, index2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
[ 本帖最后由 xjzuo 于 2007-1-18 18:58 编辑 ] |