dijkstra.m

Dijkstra最短路算法 .详细中文注释.

% Dijkstra最短路算法 %
% 作者: 杨建栋%
% 日期: 2009年1月11日%
function [path,short_distance]=Dijkstra(Input_weight,start,endpoint) 
% 输入参数:
% Input_weight-------输入边权值矩阵!
% start--------起点;
% endpoint------终点;
% 输出参数:
% path-----从起点到终点的最短路径;
% short_distance------从起点到终点的最短距离
[row,col]=size(Input_weight);

%输入参数检查
if row~=col
    error('输入错误,输入参数必须为方阵.' );
end
if endpoint>row
    error('输入终点超出最大值');
end

%初始化
s_path=[start];  %初始化路径,s_path存放起点
distance=inf*ones(1,row);distance(start)=0; %初始化距离,起点距离为0,其余为无穷
flag(start)=start; %标记起点
temp=start;

while length(s_path)<row %节点个数小于输入方阵行数时
    pos=find(Input_weight(temp, : )~=inf) %取出输入矩阵第temp行中值不是无穷的数,赋值给pos数组
    %对pos中的数进行循环,如果没有在s_path中找到,那么取
    %distance(pos(i)) = min{distance(pos(i)),distance(temp)+Input_weight(temp,pos(i))}
    for i=1:length(pos) 
        if (length(find(s_path==pos(i)))==0)&(distance(pos(i))>(distance(temp)+Input_weight(temp,pos(i))))
            distance(pos(i))=distance(temp)+Input_weight(temp,pos(i));
            %并且标记该节点的上一个节点
            flag(pos(i))=temp;
        end
    end
    %从上一步算出的距离中,找到距离最小的点.并将这个点添加到s_path中.
    k=inf;    
    for i=1:row
        if (length(find(s_path==i))==0)&(k>distance(i))
            k=distance(i);
            temp_2=i;
        end
    end
    s_path=[s_path,temp_2];
    %将找到的距离最小的节点作为下一个循环的起点
    temp=temp_2;
end

%循环结束,输出结果
path(1)=endpoint;
i=1;
while path(i)~=start
    path(i+1)=flag(path(i));
    i=i+1;
end
path(i)=start;
path=path(end:-1:1);
short_distance=distance(endpoint);