dijskshortstpathalgorithm.m

dijsk最短路径算法(matlab),求图像两点间的最短路径

%dijsk最短路径算法(matlab) 
%算法描述：
%输入图G，源点v0，输出源点到各点的最短距离D
%中间变量v0保存当前已经处理到的顶点集合，v1保存剩余的集合
%1.初始化v1,D
%2.计算v0到v1各点的最短距离，保存到D
%for each i in v0;D(j)=min[D(j),G(v0(1),i)+G(i,j)] ,where j in v1
%3.将D中最小的那一项加入到v0，并且从v1删除这一项。
%4.转到2，直到v0包含所有顶点。
%dijsk最短路径算法
clear,clc
G=[
    inf inf 10 inf 30 100;
    inf inf 5  inf inf inf;
    inf 5 inf 50 inf inf;
    inf inf inf inf inf 10;
    inf inf inf 20 inf 60;
    inf inf inf inf inf inf;
];  %邻接矩阵 
N=size(G,1); %顶点数
v0=1; %源点
v1=ones(1,N); %除去原点后的集合
v1(v0)=0;
%计算和源点最近的点
D=G(v0,:);
while 1
    D2=D;
    for i=1:N
        if v1(i)==0
            D2(i)=inf;
        end
    end
    D2
    [Dmin id]=min(D2);
    if isinf(Dmin),error,end

    v0=[v0 id] %将最近的点加入v0集合，并从v1集合中删除
    v1(id)=0;
    
    if size(v0,2)==N,break;end
    %计算v0（1）到v1各点的最近距离
    fprintf('计算v0（1）到v1各点的最近距离\n');v0,v1
    id=0;
    for j=1:N %计算到j的最近距离
        if v1(j)
            for i=1:N
                if ~v1(i) %i在vo中
                    D(j)=min(D(j),D(i)+G(i,j));
                end
                D(j)=min(D(j),G(v0(1),i)+G(i,j));
            end
        end
    end
    fprintf('最近距离\n');D
    if isinf(Dmin),error,end
end
v0

%>> v0
%v0 =
%     1     3     5     4     6