%%
%一个完美的Dijkstra算法
%改造
clear;
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+a';
%%
pb(1:length(a))=0;pb(1)=1;
%pb是一个标记第i个顶点是否已经进入S集合的标记，0代表尚未进入，1代表已经进入
index1=1;
%index_n_1：进入S的点的顺序
index2=ones(1,length(a));
%index2(i)出发点到第i点的最短通路中，第i点前一个顶点的序号
d(1:length(a))=M;d(1)=0;
%d(i)出发点到第i点的最短通路值
temp=1;
while sum(pb)<length(a)
tb=find(pb==0);%S_index
d(tb)=min(d(tb),d(temp)+a(temp,tb));
%更新距离
tmpb=find(d(tb)==min(d(tb)));%index（S中的）:S集中最短点
temp=tb(tmpb(1));%index：S集中最短点
pb(temp)=1;%把最短点加入S集
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
测试：
n=8;point=random('unif',0,5,n,2);%随机生成点
a=squareform(pdist(point));
a=a.*random('unid',5,n,n);
%欧式距离没发测试
my_Dijkstra(a)
plot(point(:,1),point(:,2),'o')
另附一个网上找的
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
