dijkstra.txt

dijkstra算法对于最短路问题的求解

% 例：
%在命令窗口输入矩阵
%clear;  A= inf*ones(6); 
%A(1,1)=0;A(1,2)=4; A(1,3)=1;
%A(2,2)=0;A(2,4)=4;A(2,5)=2;A(2,6)=4;
%A(3,2)=5; A(3,3)=0; A(3,5)=6; A(3,6)=7;
%A(4,4)=0; A(5,4)=5; A(5,5)=0;A(6,5)=3; A(6,6)=0;
%矩阵较小时可直接输入
%A=[      0  4  1   inf inf inf
    %     inf  0 inf   4  2  4
    %     inf  5  0   inf 6  7
    %     inf  inf inf  0  inf inf
    %     inf  inf inf  5  0  inf
    %     inf  inf inf  inf 3  0] ;
%v=1;%输入起点
function [l,t]=dijkstra(A,v)
%dijkstra最短路算法,l为某个顶点v到其余顶点的最短距离 t为父点
n=length(A);%顶点个数
V=1:n;%顶点集合
s=v;%已经找到最短路的点，初始为v
l=A(v,:);%当前各个点到v点的距离，初始为直接距离
t=v.*ones(1,n);%当前距离时点的父顶点，初始都为v
ss=setdiff(V,s);nn=length(ss);% 返回V中那些不属于S的元素
for j=1:n-1%一共进行n-1次迭代
    for i=1:nn%遍历当前还没有找到最短路的点
        k=ss(1);
    if l(k)>l(ss(i))
        k=ss(i);
        l(k)=l(ss(i));%取当前迭代中距离最小值
    end
    end
    if l(k)==inf%如果当前行最小值是无穷大，则结束
       break;
    else%否则k点的最短路找到
        s=union(s,k);% 返回s和k的并集
        ss=setdiff(V,s);
        nn=length(ss);
    end
    if length(s)==n%全部点的最短路都找到
       break;
    else 
        for i=1:nn%以k为生长点，如果通过k点会更短，则更改当前最短距离
            if l(ss(i))>l(k)+A(k,ss(i))
               l(ss(i))=l(k)+A(k,ss(i));
               t(ss(i))=k;  
            end
        end
    end
end
%附：运行上面程序后，如果想更清楚地观看点v到点vv的最短距离与路径可用下面小程序：
%v=1;%v要与上面的起点v一致
%vv=4;k=vv;tt=vv;
%while(1)
%if k==v
%    tt %路径vv <--...<-- v
%    l(vv) %距离
%    break;
%else
%    k=t(k);
%    tt=[tt,k];
%end
%end
在此基础上可在命令窗口依次改变起点v的值，从而计算各个点之间的相互距离。