nsizew 1skuk代表父顶点建模dijkstra算法.pdfVIP

function[lz]=dijkstra(k,w)

n=size(w,1);s=[k];u=k;%u代表的父顶点

l=w(k,:);z=u*ones(1,n);

sbu=1:n;sbu(k)=[];%代表v\s的点，既v在s的补集，记做s补

j=1;

whilejn;%j是s的向量个数，s中的顶点个数总顶点个数,循环继续

lbu=[];%用来记录v\s中顶点的权，先令为空矩阵

lv=[];%用来记录v\s中顶点，先令为空矩阵

m=size(sbu,2);%度量v\s的顶点个数

fori=1:m

ifl(sbu(i))l(u)+w(u,sbu(i));%sub（i）顶点值（是哪一个顶点）

l(sbu(i))=l(u)+w(u,sbu(i));

z(sbu(i))=u;%sub（i）的父顶点改为u

end

lbu=[lbu,l(sbu(i))];%用来记录v\s中顶点的权

lv=[lv,sbu(i)];%用来记录v\s中顶点

end

[qp]=min(lbu);%度量v\s中最小顶点的权（q）和位置（p）

u=lv(p);%改变该位置顶点的父顶点

s=[s,lv(p)];%向s中添加上个步骤中计算的父顶点

e=find(sbulv(p));%找到v\s中父顶点的位置

sbu(e)=[];%把那个父顶点从sbu中删除

j=size(s,2);%记录s中顶点的个数

end

命令窗口：

w=[050inf402510;5001520inf25;inf1501020inf;40201001025;25inf20100

55;1025inf25550]

dijkstra(1,w)

function[l,z]=dijkstra(a,w)

n=size(w,1);

%赋初值

s=[];

s(1)=a;

u=a;%初始顶点的序号和当前顶点的序号

l=w(a,:);

z=u*ones(1,n);%初始顶点路径的权，初始路径上各顶点的父亲点

k=1;

whilekn%当剩余顶点集非空时，继续

ltmp=[];

lv=[];

fori=1:n

ins=find(s==i);%查找顶点是否在s中

ifisempty(ins)%若不在s中，则更新l(v),z(v),并另存于ltmp和lv中

ifl(i)l(u)+w(u,i)

l(i)=l(u)+w(u,i);

z(i)=u;

end

ltmp=[ltmp,l(i)];%将v/s的顶点的当前权值和顶点序号

lv=[lv,i];

end

end

[lp,li]=min(ltmp);%找v*，使得l(v*)为剩余顶点集中的最小值，并令s=s+[v*]

s(k+1)=w(li);

k=k+1;

u=s(k);%为下一轮循环做准备，即u