【Dijkstra】Matlab实现



2016年05月25日    Author:Guofei

文章归类: Matlab    文章编号:

版权声明:本文作者是郭飞。转载随意,但需要标明原文链接,并通知本人
原文链接:https://www.guofei.site/2016/05/25/Dijkstra.html


%%
%一个完美的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

您的支持将鼓励我继续创作!