dijkstra.m

dijkstra算法

%%Dijkstra算法
%%vi为结点，ei为边，L为路径长度
function Dijkstra
%%输入信息
n=input('请输入结点的个数n=');
m=input('请输入边的条数m=');
for k=1:m
    bian(k).qianqu=input('边的前驱','s');
    bian(k).houji=input('边的后继','s');
    bian(k).value=input('边的权重');
end
for k=1:n
    dian(k).name=strcat('v',num2str(k));
    dian(k).biaohao='t';
end
%%初始化
dian(1).L=0;
dian(1).qianqu=0;
dian(1).biaohao='p';
for k=1:m
    if bian(k).qianqu=='v1'
        dian(str2num(bian(k).houji(2))).L=bian(k).value;
        dian(str2num(bian(k).houji(2))).qianqu=dian(1).name;
    end
    if bian(k).houji=='v1'
        dian(str2num(bian(k).qianqu(2))).L=bian(k).value;
        dian(str2num(bian(k).qianqu(2))).qianqu=dian(1).name;
    end
end
for k=1:n
    if isempty(dian(k).L)
        dian(k).L=inf;
    end
end
%%求解最短途径
log=n-1;min=inf;
while log
    for k=2:n
        if dian(k).biaohao=='t'
           if min>dian(k).L 
                mins=k;
                min=dian(k).L;
           end
        end
    end
    dian(mins).biaohao='p';
    for k=1:m
        if bian(k).qianqu==strcat('v',num2str(mins))&dian(str2num(bian(k).houji(2))).biaohao~='p'
            if dian(str2num(bian(k).houji(2))).L>(dian(str2num(bian(k).qianqu(2))).L+bian(k).value)
                dian(str2num(bian(k).houji(2))).L=dian(str2num(bian(k).qianqu(2))).L+bian(k).value;
                dian(str2num(bian(k).houji(2))).qianqu=dian(mins).name;
            end
        end
        if  bian(k).houji==strcat('v',num2str(mins))&dian(str2num(bian(k).qianqu(2))).biaohao~='p'
            if dian(str2num(bian(k).qianqu(2))).L>(dian(str2num(bian(k).houji(2))).L+bian(k).value)
                dian(str2num(bian(k).qianqu(2))).L=dian(str2num(bian(k).houji(2))).L+bian(k).value;
                dian(str2num(bian(k).qianqu(2))).qianqu=dian(mins).name;
            end
        end
    end
    min=inf;log=log-1;
end
dian(n).L
dian(n).name
p=dian(str2num(dian(n).qianqu(2)));
for k=1:(n-2)
    p.name
    p=dian(str2num(p.qianqu(2)));
end
p.name