关于Dijkstra算法的matlab代码解决思路
关于Dijkstra算法的matlab代码
实在是没办法了，求大神帮忙呀！是这样的，随机生成200个点，对每个点用Dijkstra算法求最短路径，再找出最长和次长路径，并打印，下面是代码，求帮忙呀！现在只能打印一条细呀！求救命呀！
clear;clc;
rand('state',29)
N=200;
point=44;
r=0.1526;
x=rand(N,1);
y=rand(N,1);
P=x+1i*y;
A=repmat(P,1,N)-repmat(P.',N,1);
D=abs(A);
[Ix,Iy]=find(D<r);
plot([P(Ix),P(Iy)].','o','MarkerSize',3)
hold on
plot([P(Ix) P(Iy)].')
%--------------------初始化------------------------------
Value=D;
T=find(D>r);
Value(T)=Inf;%小于r时距离为Inf
max=0;cimax=0;%最长的和次长的路径的长度
smax(1:N)=Inf;%最长的路径是哪些点
scimax(1:N)=Inf;%次长的路径是哪些点
for point=1:N%对每个点利用Dijkstra算法
Q=Value(point,:);
Front=point*ones(1,N);
V=1:N;%已知所有点
s=point;%已加入的点
ss=setdiff(V,s);nn=length(ss);%未加入的点
%利用Dijkstra算法
for i=1:N-1
%寻找现在的最小路径
k=ss(1);
for j=1:nn
if (Q(k)>Q(ss(j)))
k=ss(j);
end
end
%如果最小的距离都大于Inf，则所有的点都断开了，结束
if(Q(k)==Inf)
break;
else%最短路径找到
s=union(s,k);
ss=setdiff(V,s);
nn=length(ss);
end
if(length(s)==N)%点已经全部找到
break;
else%否则更新路径
for j=1:nn
if(Q(ss(j))>Q(k)+Value(k,ss(j)))%找到更小路径
Q(ss(j))=Q(k)+Value(k,ss(j));
Front(ss(j))=k;
end
end
end
end
%确定最长和次长路径
eee=Q(1);
%寻找对于point最长路径
for pppp=1:N
if(Q(pppp)>eee)
eee=Q(pppp);
end
end
qqq(1:N)=Inf;
k=find(Q==eee);
i=1;
while(k~=point)
qqq(i)=k;
k=Front(k);
i=i+1;
end
qqq(i)=point;
%如果point最长路径比max还长
eee;
max;
cimax;
if(eee>max)
cimax=max;
scimax=smax;
max=eee;
smax=qqq;
%point的最长路径比max短，但比次长cimax长
else if(eee<max&&eee>cimax)
cimax=eee;
scimax=qqq;
end
end
end
figure(2)
plot(x,y,'o','MarkerSize',2);
hold on
aaa=smax(smax<Inf);
plot(x(aaa),y(aaa),'r');
hold on
bbb=scimax(scimax<Inf);
plot(x(bbb),y(bbb),'k')
------解决方案--------------------
------解决方案--------------------
实在是没办法了，求大神帮忙呀！是这样的，随机生成200个点，对每个点用Dijkstra算法求最短路径，再找出最长和次长路径，并打印，下面是代码，求帮忙呀！现在只能打印一条细呀！求救命呀！
clear;clc;
rand('state',29)
N=200;
point=44;
r=0.1526;
x=rand(N,1);
y=rand(N,1);
P=x+1i*y;
A=repmat(P,1,N)-repmat(P.',N,1);
D=abs(A);
[Ix,Iy]=find(D<r);
plot([P(Ix),P(Iy)].','o','MarkerSize',3)
hold on
plot([P(Ix) P(Iy)].')
%--------------------初始化------------------------------
Value=D;
T=find(D>r);
Value(T)=Inf;%小于r时距离为Inf
max=0;cimax=0;%最长的和次长的路径的长度
smax(1:N)=Inf;%最长的路径是哪些点
scimax(1:N)=Inf;%次长的路径是哪些点
for point=1:N%对每个点利用Dijkstra算法
Q=Value(point,:);
Front=point*ones(1,N);
V=1:N;%已知所有点
s=point;%已加入的点
ss=setdiff(V,s);nn=length(ss);%未加入的点
%利用Dijkstra算法
for i=1:N-1
%寻找现在的最小路径
k=ss(1);
for j=1:nn
if (Q(k)>Q(ss(j)))
k=ss(j);
end
end
%如果最小的距离都大于Inf，则所有的点都断开了，结束
if(Q(k)==Inf)
break;
else%最短路径找到
s=union(s,k);
ss=setdiff(V,s);
nn=length(ss);
end
if(length(s)==N)%点已经全部找到
break;
else%否则更新路径
for j=1:nn
if(Q(ss(j))>Q(k)+Value(k,ss(j)))%找到更小路径
Q(ss(j))=Q(k)+Value(k,ss(j));
Front(ss(j))=k;
end
end
end
end
%确定最长和次长路径
eee=Q(1);
%寻找对于point最长路径
for pppp=1:N
if(Q(pppp)>eee)
eee=Q(pppp);
end
end
qqq(1:N)=Inf;
k=find(Q==eee);
i=1;
while(k~=point)
qqq(i)=k;
k=Front(k);
i=i+1;
end
qqq(i)=point;
%如果point最长路径比max还长
eee;
max;
cimax;
if(eee>max)
cimax=max;
scimax=smax;
max=eee;
smax=qqq;
%point的最长路径比max短，但比次长cimax长
else if(eee<max&&eee>cimax)
cimax=eee;
scimax=qqq;
end
end
end
figure(2)
plot(x,y,'o','MarkerSize',2);
hold on
aaa=smax(smax<Inf);
plot(x(aaa),y(aaa),'r');
hold on
bbb=scimax(scimax<Inf);
plot(x(bbb),y(bbb),'k')
------解决方案--------------------
------解决方案--------------------